题目描述
有一个n×m 的棋盘,在某个点 (x, y) 上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步。
输入
输入只有一行四个整数,分别为 n, m, x, y。
输出
一个n×m 的矩阵,代表马到达某个点最少要走几步(不能到达则输出−1)。
样例输入
3 3 1 1
样例输出
0 3 2 3 -1 1 2 1 4
提示
bfs板子题
#include<bits/stdc++.h> using namespace std; queue <int> x; queue <int> y; queue <int> s; int dx[9]={0,-1,-2,-2,-1,1,2,2,1}; int dy[9]={0,-2,-1,1,2,2,1,-1,-2}; int mp[500][500],vis[500][500],m,n,sx,sy; int main() { cin>>m>>n>>sx>>sy; x.push(sx);//记录x坐标 y.push(sy);//记录y坐标 s.push(0);//记录所用步数 while(!x.empty()) { int tx=x.front(); int ty=y.front(); int ts=s.front(); x.pop(); y.pop(); s.pop(); for(int i=1;i<=8;++i) { int xx=tx+dx[i]; int yy=ty+dy[i]; if(xx>0&&yy>0&&xx<=m&&yy<=n&&vis[xx][yy]==0&&mp[xx][yy]==0)
//对⑧个方向遍历 如果第一次到达就记录下步数 { x.push(xx); y.push(yy); s.push(ts+1);
//储存新标记的的点 vis[xx][yy]=1; mp[xx][yy]=ts+1; } } } mp[sx][sy]=0; for(int i=1;i<=m;++i) { for(int j=1;j<=n;++j) { if(vis[i][j]==1) { printf("%-5d",mp[i][j]);
//注意输出格式 } else { printf("%-5d",-1); } } cout<<endl; } return 0; }
标签:遍历,int,yy,xx,sx,push,500 From: https://www.cnblogs.com/XdzxBo/p/16622432.html