广搜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};坐标入队时马上更新步数即可
  

参考代码

1. #include <bits/stdc++.h>
2. using namespace std;
3. const int MAXN = 405;
4. void bfs(int x,int y);
5. int m,n;//n行m列
6. struct node{
7.         int x,y;
8. };
9. queue <node> q;
10. int zx[] = {1,1,-1,-1,2,2,-2,-2} ;
11. int zy[] = {2,-2,2,-2,1,-1,1,-1};
12. bool f[MAXN][MAXN] = {false};
13. int ans[MAXN][MAXN] ;
14. int main(){
15.         int x0,y0;
16.         cin>>n>>m>>x0>>y0;
17.         bfs(x0,y0) ;
18.         return 0;
19. }
20. void bfs(int x,int y){
21.         //node k = (x,y);//直接创建一个结构体 -这种建法需要做自定义函数
22.         node k = node{x,y} ;
23.         q.push(k);
24.         f[x][y] = true;
25.         while(!q.empty()){
26.                 int x1 = q.front().x,y1 = q.front().y ;//取出队首
27.                 q.pop();//弹出队首
28.                 for(int i=0;i<8;i++){
29.                         int nx = x1+zx[i],ny = y1+zy[i];//忘八个方向遍历
30.                         if(nx<1||nx>n||ny<1||ny>m||f[nx][ny]) continue;//越界或者被访问过则访问下一个点
31.                         q.push((node){nx,ny});//该点入队
32.                         ans[nx][ny] = ans[x1][y1]+1 ; //该点一定是马从（x1,y1）点走过来的
33.                         f[nx][ny] = true;//标记
34.                 }
35.         }
36.         //输出答案
37.         for(int i=1;i<=n;i++){
38.                 for(int j=1;j<=m;j++){
39.                         if(f[i][j] ) cout<<ans[i][j]<<" ";
40.                         else cout<<-1<<" ";//没被访问过说明没办法走到，-1
41.                 }
42.                 cout<<endl;
43.         }
44.         return ;
45. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。