洛谷P1443 马的遍历

简单的bfs

题目链接

P1443 马的遍历 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

有一个 n×m 的棋盘，在某个点(x,y) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

输入格式

输入只有一行四个整数，分别为 n,m,x,y。

输出格式

一个 n×m 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 −1）。

题解

#include<bits/stdc++.h>
using namespace std;
int mapp[500][500];
int i,j,m,n;struct Node
{int x,y,now;
}node;
queue<Node > ssr;
bool boom(int x1,int y1)
{if(x1<=0||y1<=0||x1>n||y1>m||mapp[x1][y1]!=-1){return false;}return true;
}
int bfs()
{Node a1;if(!ssr.empty()){a1=ssr.front();ssr.pop();}else{return 0;}Node node0;if(boom(a1.x+1,a1.y+2)){node0.x=a1.x+1;node0.y=a1.y+2;node0.now=a1.now+1;mapp[node0.x][node0.y]=node0.now;ssr.push(node0);}if(boom(a1.x-1,a1.y+2)){node0.x=a1.x-1;node0.y=a1.y+2;node0.now=a1.now+1;mapp[node0.x][node0.y]=node0.now;ssr.push(node0);}if(boom(a1.x+1,a1.y-2)){node0.x=a1.x+1;node0.y=a1.y-2;node0.now=a1.now+1;mapp[node0.x][node0.y]=node0.now;ssr.push(node0);}if(boom(a1.x-1,a1.y-2)){node0.x=a1.x-1;node0.y=a1.y-2;node0.now=a1.now+1;mapp[node0.x][node0.y]=node0.now;ssr.push(node0);}if(boom(a1.x-2,a1.y-1)){node0.x=a1.x-2;node0.y=a1.y-1;node0.now=a1.now+1;mapp[node0.x][node0.y]=node0.now;ssr.push(node0);}if(boom(a1.x-2,a1.y+1)){node0.x=a1.x-2;node0.y=a1.y+1;node0.now=a1.now+1;mapp[node0.x][node0.y]=node0.now;ssr.push(node0);}if(boom(a1.x+2,a1.y+1)){node0.x=a1.x+2;node0.y=a1.y+1;node0.now=a1.now+1;mapp[node0.x][node0.y]=node0.now;ssr.push(node0);}if(boom(a1.x+2,a1.y-1)){node0.x=a1.x+2;node0.y=a1.y-1;node0.now=a1.now+1;mapp[node0.x][node0.y]=node0.now;ssr.push(node0);}return 1;
}
int main()
{memset(mapp,-1,sizeof(mapp));cin>>n>>m>>i>>j;mapp[i][j]=0;node.x=i;node.y=j;node.now=0;ssr.push(node);while(bfs()){}for(int i1=1;i1<=n;i1++){int key=0;for(int j1=1;j1<=m;j1++){cout<<mapp[i1][j1]<<" ";}cout<<endl;}return 0;
}