O1482 【基础】骑士巡游

*原理：

dfs：

#include <bits/stdc++.h>
using namespace std;
//棋盘大小及起止位置 
int n,m,s1,s2,t1,t2;
int a[10][10];//存放棋盘
int d[10][10];//到每个位置的最短路径 

//dep：到该点的步数 
void fun(int x,int y,int dep){
	//如果走到这个位置的步数比假设的少（也可以防止死循环） 
	if(dep < d[x][y]){
		d[x][y] = dep;
		//八个方向探测
		if(x-1>=1&&y-2>=1) fun(x-1,y-2,dep+1); 
		if(x-2>=1&&y-1>=1) fun(x-2,y-1,dep+1);
		if(x-2>=1&&y+1<=m) fun(x-2,y+1,dep+1);
		if(x-1>=1&&y+2<=m) fun(x-1,y+2,dep+1);
		if(x+1<=n&&y+2<=m) fun(x+1,y+2,dep+1);
		if(x+2<=n&&y+1<=m) fun(x+2,y+1,dep+1);
		if(x+2<=n&&y-1>=1) fun(x+2,y-1,dep+1);
		if(x+1<=n&&y-2>=1) fun(x+1,y-2,dep+1); 
	}	
}

int main(){
	cin>>n>>m>>s1>>s2>>t1>>t2;
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			d[i][j] = INT_MAX;//先设置为最大 
		}
	}
	fun(s1,s2,0);
	cout<<d[t1][t2]<<endl;
}

bfs:

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,s,tt,a[10][10];
int dx[]{0,1,2,2,1,-1,-2,-2,-1};
int dy[]{0,2,1,-1,-2,-2,-1,1,2};
struct node{
	int x,y,cnt;
};
bool check(int x,int y){
	if(x<1||y<1)return false;
	return true;
}
void bfs(){
	queue<node> q;
	q.push((node){x,y,0});
	while(!q.empty()){
		node t=q.front();
		q.pop();
		int nx=t.x,ny=t.y;
		if(nx==s&&ny==tt){
			cout << t.cnt;
			return ;
		}
		for(int i = 1;i <= 8;i++){
			int X=nx+dx[i];
			int Y=ny+dy[i];
			if(check(X,Y)){
				q.push((node){X,Y,t.cnt+1});
//				cout << X << " " << Y<< endl;//
			}
		}
	}
}
signed main(){
	cin >>n>>m>>x>>y>>s>>tt;
	bfs();
	return 0;
}
/*
3 3 1 1 1 3
*/