广搜bfs-P1443 马的遍历

P1443 马的遍历

题目来源-洛谷

题意

要求马到达棋盘上任意一个点最少要走几步

思路

• 国际棋盘规则是马的走法是-日字形，也称走马日，即x,y一个是走两步，一个是一步

• 要求最小步数，所以考虑第一次遍历到的点即为最小步数，即bfs宽搜处理

• 套模板，遍历的可能即为当前位置的不同走法，借助数组来处理

  int zx[] = {1,1,-1,-1,2,2,-2,-2} ; int zy[] = {2,-2,2,-2,1,-1,1,-1};坐标入队时即刻更新步数即可

参考代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 405;
void bfs(int x,int y);
int m,n;//n行m列
struct node{int x,y;
};
queue <node> q;
int zx[] = {1,1,-1,-1,2,2,-2,-2} ;
int zy[] = {2,-2,2,-2,1,-1,1,-1};
bool f[MAXN][MAXN] = {false};
int ans[MAXN][MAXN] ;
int main(){int x0,y0; cin>>n>>m>>x0>>y0;bfs(x0,y0) ;return 0;
}
void bfs(int x,int y){//node k = (x,y);//直接创建一个结构体 -这种建法需要做自定义函数 node k = node{x,y} ;q.push(k);f[x][y] = true;while(!q.empty()){int x1 = q.front().x,y1 = q.front().y ;//取出队首 q.pop();//弹出队首 for(int i=0;i<8;i++){int nx = x1+zx[i],ny = y1+zy[i];//忘八个方向遍历 if(nx<1||nx>n||ny<1||ny>m||f[nx][ny]) continue;//越界或者被访问过则访问下一个点q.push((node){nx,ny});//该点入队 ans[nx][ny] = ans[x1][y1]+1 ; //该点一定是马从（x1,y1）点走过来的 f[nx][ny] = true;//标记 }}//输出答案for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(f[i][j] ) cout<<ans[i][j]<<" ";else cout<<-1<<" ";//没被访问过说明没办法走到，-1 }cout<<endl;} return ;
}