HRBUST 1181 移动 bfs模板

分手后的思念是犯贱 2022-01-06 11:45 137阅读 0赞

1 #include<bits/stdc++.h>///该头文件为万能头文件，有些学校oj不能使用，读者可根据需要自行修改
     2 using namespace std;
     3 const int MAXN=305;
     4 int vis[MAXN][MAXN];
     5 int X[9]={
        0,-2,-1,-2,-1,1,2,2,1};
     6 int Y[9]={
        0,-1,-2,1,2,2,1,-1,-2};
     7 struct point
     8 {
     9     int x;
    10     int y,step;
    11 };
    12 queue<point>q;
    13 
    14  int xx1,yy1,x2,y2;
    15   int res;
    16 void bfs()
    17 {
    18     vis[xx1][yy1]=1;//1
    19     point a;
    20     a.x=xx1;
    21     a.y=yy1;
    22     a.step=0;
    23     q.push(a);//2
    24     while(!q.empty())//3
    25     {
    26         point head=q.front();//4
    27         q.pop();
    28         if(head.x==x2&&head.y==y2)//5
    29         {
    30             //若找到需要的点则结束循环并返回
    31              res=head.step;
    32              return;
    33         }
    34  
    35         else
    36         {
    37  
    38           for(int i=1;i<=8;i++)//6
    39           {
    40               point t;
    41               t.x=head.x+X[i];
    42               t.y=head.y+Y[i];
    43               if(t.x>=0&&t.x<=300&&t.y>=0&&t.y<=300&&vis[t.x][t.y]==0)///把八个方向都放到队列中去
    44               {
    45                   vis[t.x][t.y]=1;///每一步都等于其上一步+1
    46                   t.step=head.step+1;
    47                   //printf("x=%d y=%d\n",t.x,t.y);
    48                   q.push(t);
    49               }
    50           }
    51         }
    52     }
    53 }
    54 int main()
    55 {
    56   
    57     while(~scanf("%d %d %d %d",&xx1,&yy1,&x2,&y2))
    58     {
    59         memset(vis,0,sizeof(vis));
    60         while(!q.empty())///清空队列
    61         {
    62             q.pop();
    63         }
    64        bfs();
    65         printf("%d\n",res);
    66     }
    67     return 0;
    68 }

转载于:https://www.cnblogs.com/fudanxi/p/10582277.html