信息学奥赛一本通T1330-最少步数

解题思路:BFS

注意事项:

参考代码:

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N = 1e3 +10;
int a[N][N],x1,y1,x2,y2;
bool v[N][N];
struct node{
	int x, y;
};
int d[12][2] = {{-1,-2},{-2,-2},{-2,-1},{-2,1},{-2,2},{-1,2},{1,2},{2,2},{2,1},{2,-1},{2,-2},{1,-2}};
queue<node> q;
void bfs(int x, int y){
	q.push(node{x,y});
	v[x][y] = true;
	while(!q.empty()){
		node nd = q.front();
		q.pop();
		for(int i = 0; i < 12; i ++){
			int nx = nd.x + d[i][0];
			int ny = nd.y + d[i][1];
			if(nx > 0 && nx <= 100 && ny > 0 && ny <= 100 && !v[nx][ny]){
				v[nx][ny] = true;
				q.push(node{nx,ny});
				if(a[nx][ny] > a[nd.x][nd.y] + 1) a[nx][ny] = a[nd.x][nd.y] + 1;
			}
		}
	}
}
int main()
{	
	memset(a,0x3f,sizeof(a));
	cin >> x1 >> y1 >> x2 >> y2;
	a[x1][y1] = 0;
	bfs(x1,y1);
	cout << a[1][1] << endl;
	memset(a,0x3f,sizeof(a));
	memset(v,0,sizeof(v));
	a[x2][y2] = 0;
	bfs(x2,y2);
	cout << a[1][1];
	return 0;
}