蓝桥杯备考：bfs之马的遍历

像这种最短路径啊，我们一般都是用的bfs来求

像这道题，我们要定义dxdy两个方向向量

然后我们先把起点放在队列里面，然后把起点出队列，把最短路径是1的点放在队列里面，然后在再依次把最短路径是1的点出队列，把最短路径是2的点代入队列，一直到队列里没有元素时截至，进队列的同时我们要把这个队列的最短路径存到二维数组里面

方向向量的选择

BFS遍历过程

下面我们来展示代码

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 410;
int path[N][N];
typedef pair<int,int> PII;
int n,m,x,y;
int dx[] = {1, 2, 2, 1, -1, -2, -2, -1};
int dy[] = {2, 1, -1, -2, -2, -1, 1, 2};
void bfs()
{
	queue <PII> q;
	q.push({x,y});
	path[x][y] = 0;
	
	while(q.size())
	{
	 	auto t = q.front();q.pop();
	 	int px = t.first; int py = t.second;
		for(int i = 0;i<=7;i++)
		{
			int x = px+dx[i];int y = py+dy[i];
			if(x<1 || x>n || y<1 || y>m) continue;
			if(path[x][y]!=-1) continue;
			path[x][y] = path[px][py]+1;
			q.push({x,y});
		} 
	}
	
}
int main()
{
	cin >> n >> m >> x >> y;
	memset(path,-1,sizeof path);
	bfs();
	for(int i = 1;i<=n;i++)
	{
		for(int j = 1;j<=m;j++)
		{
			cout << path[i][j] << " ";
		}
		cout << endl;
	}
	
	
	
	
	
	return 0;
}