题目描述
有一个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
一道比较明显的广度优先搜索题，可以发现，起始点值为0，当马第一次跳到哪个点时就是哪个点应该标记的值，并且后续跳到同一个点后会重复循环，一定不是最优解，所以只需保留每个点的第一次遍历到的状态即可，如果发现当前遍历到的点已经被遍历过了，就跳过此点，继续扩展，知道没有可以扩展的点，即所有可能的点都已被遍历过，而遍历不到的点只需在开始时将矩阵初始化为-1就可以保证正确了。
但是题中还有一个条件，就是输出“左对齐，宽5格”，两个条件都可以用printf搞定，只需在“%”与“d”间加上“-5”即可，“-”代表左对齐，“5”代表输出宽5格，还有一个小技巧就是可以再“5”前加“0”，这样可以补足5位前导0，但是注意与“-”左对齐共同使用并无卵用
上代码：
#include<cstdio>
#include<iostream>
using namespace std;
int n,m,sy,sx,head,tail,ty,tx;
int map[][];
struct que{
int y,x,step;
}q[];
int main(){
scanf("%d%d%d%d",&n,&m,&sy,&sx);
for(int i=;i<=n;i++){//先初始化为-1
for(int j=;j<=m;j++){
map[i][j]=-;
}
}
head=tail=;
map[sy][sx]=;
q[tail].y=sy;
q[tail].x=sx;
q[tail++].step=;
while(head<tail){
ty=q[head].y;
tx=q[head].x;
if(map[ty-][tx+]==-){//向马能跳到的八个方向遍历
//-1判断是否仍未遍历过，保证是第一次遍历
q[tail].y=ty-;
q[tail].x=tx+;
q[tail].step=q[head].step+;
map[ty-][tx+]=q[tail].step;
tail++;
}
if(map[ty-][tx+]==-){
q[tail].y=ty-;
q[tail].x=tx+;
q[tail].step=q[head].step+;
map[ty-][tx+]=q[tail].step;
tail++;
}
if(map[ty+][tx+]==-){
q[tail].y=ty+;
q[tail].x=tx+;
q[tail].step=q[head].step+;
map[ty+][tx+]=q[tail].step;
tail++;
}
if(map[ty+][tx+]==-){
q[tail].y=ty+;
q[tail].x=tx+;
q[tail].step=q[head].step+;
map[ty+][tx+]=q[tail].step;
tail++;
}
if(map[ty+][tx-]==-){
q[tail].y=ty+;
q[tail].x=tx-;
q[tail].step=q[head].step+;
map[ty+][tx-]=q[tail].step;
tail++;
}
if(map[ty+][tx-]==-){
q[tail].y=ty+;
q[tail].x=tx-;
q[tail].step=q[head].step+;
map[ty+][tx-]=q[tail].step;
tail++;
}
if(map[ty-][tx-]==-){
q[tail].y=ty-;
q[tail].x=tx-;
q[tail].step=q[head].step+;
map[ty-][tx-]=q[tail].step;
tail++;
}
if(map[ty-][tx-]==-){
q[tail].y=ty-;
q[tail].x=tx-;
q[tail].step=q[head].step+;
map[ty-][tx-]=q[tail].step;
tail++;
}
head++;
}
for(int i=;i<=n;i++,puts("")){
for(int j=;j<=m;j++){
printf("%-5d",map[i][j]);//左对齐 宽5格
}
}
return ;
}