https://www.luogu.com.cn/problem/P1443
题目描述
有一个n*m的棋盘(1<n,m<=400)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步
输入格式
一行四个数据，棋盘的大小和马的坐标
输出格式
一个n*m的矩阵，代表马到达某个点最少要走几步（左对齐，宽5格，不能到达则输出-1）
输入输出样例
输入 #1复制
代码语言：javascript复制3 3 1 1输出 #1复制
代码语言：javascript复制0 3 2
3 -1 1
2 1 4 题解：一般情况下的BFS，每个能走的方向都保存下来，更新需要输出的地图。BFS的写法就是一般的写法，注意的是输出时需要宽5格。一开始用了cin，不太熟练使用格式化输出，就改成了scanf/printf输入输出了。
代码语言：javascript复制#include <stdio.h>
#include <string.h>
#include<bits/stdc .h>
using namespace std;
typedef long long ll;
int mp[410][410];
int vis[410][410];
struct node
{
int x,y,step;
} w,l;
int dx[] = {-1,-1,-2,-2,1,1,2,2};
int dy[] = {-2,2,-1,1,-2,2,1,-1};
void bfs(int sx, int sy,int n, int m)
{
memset(vis,0,sizeof(vis));
memset(mp,-1,sizeof(mp));
queue<node>q;
w.x = sx;
w.y = sy;
w.step = 0;
q.push(w);
vis[w.x][w.y] = 1;
mp[sx][sy] = 0;
while(!q.empty())
{
w = q.front();
q.pop();
for(int i = 0; i < 8; i )
{
int tx = dx[i] w.x;
int ty = dy[i] w.y;
if(tx >= 1 && tx <= n && ty >= 1 && ty <= m && vis[tx][ty] == 0)
{
l.x = tx;
l.y = ty;
l.step = w.step 1;
q.push(l);
vis[tx][ty] = 1;
mp[tx][ty] = l.step;
}
}
}
}
int main()
{
int n,m,sx,sy;
// cin >> n >> m >> sx >> sy;
scanf("%d %d %d %d", &n,&m,&sx,&sy);
bfs(sx,sy,n,m);
for(int i = 1; i <= n; i )
{
for(int j = 1; j <= m; j )
{
// if(j == 1)
// cout << mp[i][j];
// else
// cout << " " << mp[i][j] ;
printf("%-5d",mp[i][j]);
}
printf("n");
}
return 0;
}
