题目描述
有一个n*m的棋盘(1<n,m<=400)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步
输入输出格式
输入格式：
一行四个数据，棋盘的大小和马的坐标
输出格式：
一个n*m的矩阵，代表马到达某个点最少要走几步（左对齐，宽5格，不能到达则输出-1）
题解
//其中有好多重复标记的地方，请见谅 #include<bits/stdc++.h> using namespace std; queue <int> qx;//横坐标队列 queue <int> qy;//纵坐标队列 //我才不会告诉你是我懒得写结构体了呢 int dx[9]={0,+2,+2,+1,+1,-1,-1,-2,-2}; int dy[9]={0,+1,-1,+2,-2,+2,-2,+1,-1};//搜索时更改坐标 int bx,by;//变换后的坐标 int sx,sy;//起始坐标 int nx,ny;//现在的坐标 int n,m;//棋盘大小 int ans[401][401];//答案数组 bool bo[401][401];//判断是否走过 false表示不能走，反之能走 void bfs(int x,int y);//BFS int main(){ cin>>n>>m; memset(bo,false,sizeof(bo)); //都不能走 可以一会在判断越界的时候少写几行... for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) ans[i][j]=-1; //答案数组置为-1，若没有被更新则还是-1，可以直接输出 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) bo[i][j]=true; //输入的范围内能走 cin>>sx>>sy; bfs(sx,sy); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(j==m) {printf("%-5d ",ans[i][j]);} else {printf("%-5d",ans[i][j]);}//输出 return 0; } void bfs(int x,int y){ ans[x][y]=0;//起点步数为0 qx.push(x);//加入队列 qy.push(y); while(!qx.empty()){ //队列非空 nx=qx.front(); //取出节点对其拓展 qx.pop(); //删除节点 ny=qy.front(); qy.pop(); bo[nx][ny]=false; //标记为不能走 for(int i=1;i<=8;i++){ bx=nx+dx[i]; //将要判断的节点 by=ny+dy[i]; if(bo[bx][by]==true){//判断可走 qx.push(bx); qy.push(by); bo[bx][by]=false; //不同起步可能指向相同节点 必须操作后马上就标记避免重复入队 不要担心重复标记 标了没事 不标大概率会T （我之前T了三次，还是看dalao题解才发现的...） ans[bx][by]=ans[nx][ny]+1; } } } }