题目描述

传送门：https://www.luogu.com.cn/problem/P1443
有一个n*m的棋盘(1<n,m<=400)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步

输入格式

一行四个数据，棋盘的大小和马的坐标

输出格式

一个n*m的矩阵，代表马到达某个点最少要走几步（左对齐，宽5格，不能到达则输出-1）

输入样例

3 3 1 1

输出样例

0    3    2    
3    -1   1    
2    1    4    

棋盘最少步数到达某个点，比较常见的广度优先搜索（BFS）。首先马走日，体现在棋盘上，就是在不越界的情况下遍历八个方向，这个以dx，dy数组定义方向。首先将马的节点入队，该点记录步数为0，同时vis数组记录已经访问。之后遍历八个方向，如果满足条件，将新节点入队，同时该节点步数为上一个节点步数加1，vis数组记录已遍历，直至队列为空，将马可以走到的点全部遍历完。
题目为比较常规的BFS，首先初始化棋盘均为-1，即初始状态全部不可达，最后输出注意左对齐的输出，这里使用printf的“-5d"格式化输出。

#include<bits/stdc++.h>
using namespace std;
int dx[] = { 2,2,-2,-2,1,1,-1,-1 };
int dy[] = { -1,1,-1,1,-2,2,2,-2 };
struct point
{
	int x, y;
}node;
point top;
queue<point>que;
int n, m, hx, hy;
int mapp[405][405];
bool vis[405][405];

void bfs(int x, int y)
{
	mapp[x][y] = 0;
	vis[x][y] = true;//已入队
	node.x = x;
	node.y = y;
	que.push(node);
	while (!que.empty())
	{
		top = que.front();//头节点获取
		que.pop();//出队
		for (int i = 0; i < 8; i++)
		{
			int newx = top.x + dx[i];
			int newy = top.y + dy[i];
			if (newx<1 || newx>n || newy<1 || newy>m) continue;
			if (!vis[newx][newy])
			{
				node.x = newx;
				node.y = newy;
				//cout << node.x << " " << node.y << endl;
				que.push(node);
				vis[newx][newy] = true;
				mapp[newx][newy] = mapp[top.x][top.y] + 1;
			}
		}
	}
}

int main()
{

	cin >> n >> m >> hx >> hy;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			mapp[i][j] = -1;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			vis[i][j] = false;
	bfs(hx, hy);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++)
			printf("%-5d", mapp[i][j]);
		cout << endl;
	}
		return 0;
}