小A与小B-（双向bfs）

链接：https://ac.nowcoder.com/acm/contest/549/G
来源：牛客网

题目描述

小A与小B这次两个人都被困在了迷宫里面的两个不同的位置，而他们希望能够迅速找到对方，然后再考虑如何逃离迷宫的事情。小A每次可以移动一个位置，而小B每次可以移动两次位置，小A移动的方向是上下左右左上左下右上右下8个方向，小B移动的方向是上下左右4个方向，请问他们最早什么时候能够找到对方，如果他们最终无法相遇，那么就输出”NO"。

输入描述:

输出描述:

如果可以相遇，第一行输出一个YES，第二行一个整数输出最短的相遇时间。
否则就输出一个NO表示不能相遇。

示例1

输入

4 5
. . . . .
. # # # .
. . . # D
. . C # .

输出

YES
3

备注:

  1 #include<stdio.h>
  2 #include<iostream>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<math.h>
  6 #include<string>
  7 #include<queue>
  8 #define ll long long
  9 #define inf 0x3f3f3f3f
 10 using namespace std;
 11 
 12 struct node
 13 {
 14     int x;
 15     int y;
 16 };
 17 int n,m,ans;
 18 int ax,ay,bx,by,cnt;
 19 char mp[1005][1005];
 20 int vis[2][1005][1005];///判断是否走过，顺便记录走到这一步的步数
 21 int d0[8][2]={-1,-1, -1,0, -1,1, 0,-1, 0,1, 1,-1, 1,0, 1,1};///A的位移
 22 int d1[4][2]={-1,0, 1,0, 0,-1, 0,1};///B的位移
 23 queue<node>que[2];///0表示A,1表示B
 24 
 25 void bfs0()
 26 {
 27     while(!que[0].empty()) que[0].pop();
 28     que[0].push( {ax,ay} );
 29     while(!que[0].empty())
 30     {
 31         node now=que[0].front();
 32         int cnt=vis[0][now.x][now.y];///走到这一步的步数
 33         que[0].pop();
 34         for(int i=0;i<8;i++)
 35         {
 36             int xx=now.x+d0[i][0];
 37             int yy=now.y+d0[i][1];
 38             if( xx>=1 && xx<=n && yy>=1 && yy<=m && mp[xx][yy]=='.' && vis[0][xx][yy]==-1 )
 39             {
 40                 que[0].push( {xx,yy} );
 41                 vis[0][xx][yy]=cnt+1;///位移+1
 42             }
 43         }
 44     }
 45 }
 46 
 47 void bfs1()
 48 {
 49     while(!que[1].empty()) que[1].pop();
 50     que[1].push( {bx,by} );
 51     while(!que[1].empty())
 52     {
 53         node now=que[1].front();
 54         que[1].pop();
 55         int cnt=vis[1][now.x][now.y];
 56         for(int i=0;i<4;i++)///第一步
 57         {
 58             int xx=now.x+d1[i][0];
 59             int yy=now.y+d1[i][1];
 60             if(xx>=1 && xx<=n && yy>=1 && yy<=m && mp[xx][yy]=='.' && vis[1][xx][yy]==-1 )
 61             {
 62                 vis[1][xx][yy]=cnt+1;///第一步也要记录位移次数，与第二步的次数一样
 63                 for(int j=0;j<4;j++)///第二步在if大括号里，否则会窗墙
 64                 {
 65                     int tx=xx+d1[j][0];
 66                     int ty=yy+d1[j][1];
 67 
 68                     if( tx>=1 && tx<=n && ty>=1 && ty<=m && mp[tx][ty]=='.' && vis[1][tx][ty]==-1 )
 69                     {
 70                         que[1].push( {tx,ty} );
 71                         vis[1][tx][ty]=cnt+1;///位移次数+1
 72                     }
 73                 }
 74             }
 75         }
 76     }
 77 }
 78 
 79 
 80 int main()
 81 {
 82     memset(vis,-1,sizeof(vis));
 83     scanf("%d %d",&n,&m);
 84     for(int i=1;i<=n;i++)
 85         for(int j=1;j<=m;j++)
 86     {
 87         cin>>mp[i][j];
 88         if(mp[i][j]=='C') ax=i,ay=j;
 89         if(mp[i][j]=='D') bx=i,by=j;
 90     }
 91     vis[0][ax][ay]=0;
 92     vis[1][bx][by]=0;///起点为0
 93     bfs0();
 94     bfs1();
 95 /**打印观察
 96     for(int i=1;i<=n;i++)
 97     {
 98         for(int j=1;j<=m;j++)
 99         printf("%2d ",vis[0][i][j]);
100         printf("
");
101     }
102     printf("

");
103     for(int i=1;i<=n;i++)
104     {
105         for(int j=1;j<=m;j++)
106         printf("%2d ",vis[1][i][j]);
107         printf("
");
108     }
109 */
110     int ans=inf;
111     for(int i=1;i<=n;i++)
112         for(int j=1;j<=m;j++)
113     {
114         if( vis[0][i][j]!=-1 && vis[1][i][j]!=-1 )
115             ans = min( max(vis[0][i][j],vis[1][i][j]), ans );
116     }
117     if(ans!=inf)
118         printf("YES
%d
",ans);
119     else
120         printf("NO
");
121     return 0;
122 }