https://www.luogu.org/problemnew/show/P1443
题目描述
有一个n*m的棋盘(1<n,m<=400)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步
输入输出格式
输入格式：
一行四个数据，棋盘的大小和马的坐标
输出格式：
一个n*m的矩阵，代表马到达某个点最少要走几步（左对齐，宽5格，不能到达则输出-1）
输入输出样例
输入样例#1： 复制
3 3 1 1
输出样例#1： 复制
0 3 2
3 -1 1
2 1 4 解题思路：
从起点开始遍历马能去的位置，同时更新步数。需要注意的是-1占了两个位置。
#include <stdio.h>
#define N 450
int a[N][N],book[N][N];
int next[8][2]={
-1,-2, -2,-1, -1,2, 2,-1, 2,1, 1,2, 1,-2, -2,1
};
struct data{
int x;
int y;
}s[N*N];
int n,m;
void bfs(int x, int y)
{
book[x][y] = 1;
int tx,ty,i,head,tail;
head=0;
tail=1;
s[head].x = x;
s[head].y = y;
while(head < tail)
{
for(i=0; i<8; i++)
{
tx = s[head].x + next[i][0];
ty = s[head].y + next[i][1];
if(tx <= n && ty <= m && tx > 0 && ty > 0 && book[tx][ty] == 0)
{
book[tx][ty] = 1;
s[tail].x = tx;
s[tail].y = ty;
a[tx][ty] = a[s[head].x][s[head].y] + 1;
tail++;
}
}
head++;
}
}
int main()
{
int x,y,i,j;
scanf("%d%d%d%d", &n, &m, &x, &y);
bfs(x,y);
for(i=1; i<=n; i++)
{
for(j=1; j<=m; j++)
if(a[i][j] || i==x && j==y)
printf("%-5d",a[i][j]);
else
printf("-1 ");
printf("
");
}
return 0;
}