每日一题 6月5日 小A与小B 双向bfs

题目链接：https://ac.nowcoder.com/discuss/435795
题目大意：

思路：
1.直接对bfs，记录f[i][j]：A到(i, j)的最小时间。然后B在bfs时就可以统计答案了。
2.当然可以双向bfs。

1.
#include <bits/stdc++.h>
#define LL long long
using namespace std;

char a[1005][1005];
int xx[]={0, 0, 1, -1, -1, -1, 1, 1};
int yy[]={1, -1, 0, 0, 1, -1, -1, 1};
struct node{
    int x, y, t;
};
queue<node> q;
int vis[1005][1005], f[1005][1005], ans=1<<30;
int n, m;

void BFS1(int x, int y){
    memset(vis, 0, sizeof(vis));
    memset(f, -1, sizeof(f));
    q.push(node{x, y, 0});
    vis[x][y]=1;
    while(!q.empty()){
        node now=q.front(); q.pop();
        f[now.x][now.y]=now.t;
        for(int i=0; i<8; i++){
            int x=now.x+xx[i], y=now.y+yy[i];
            if(!vis[x][y]&&a[x][y]!='#'&&x>=1&&x<=n&&y>=1&&y<=m){
                q.push(node{x, y, now.t+1}); vis[x][y]=1;
            }
        }
    }
}

void BFS2(int x, int y){
    memset(vis, 0, sizeof(vis));
    q.push(node{x, y, 0});
    vis[x][y]=1;
    while(!q.empty()){
        node now=q.front(); q.pop();
        if(f[now.x][now.y]!=-1){
            ans=min(ans, max((now.t+1)/2, f[now.x][now.y]));
        }

        for(int i=0; i<4; i++){
            int x=now.x+xx[i], y=now.y+yy[i];
            if(!vis[x][y]&&a[x][y]!='#'&&x>=1&&x<=n&&y>=1&&y<=m){
                q.push(node{x, y, now.t+1}); vis[x][y]=1;
            }
        }
    }
}

int main(){
    scanf("%d%d%*c", &n, &m);
    int sx, sy, tx, ty;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            scanf("%c%*c", &a[i][j]);
            if(a[i][j]=='C'){
                sx=i, sy=j;
            }
            if(a[i][j]=='D'){
                tx=i, ty=j;
            }
        }
    }
    BFS1(sx, sy);
    BFS2(tx, ty);
    if(ans==1<<30){
        printf("NO\n");
    }
    else{
        printf("YES\n");
        printf("%d\n", ans);
    }

    return 0;
}
*************************************
2.
#include <bits/stdc++.h>
#define LL long long
using namespace std;

char a[1005][1005];
int xx[]={0, 0, 1, -1, -1, -1, 1, 1};
int yy[]={1, -1, 0, 0, 1, -1, -1, 1};
struct node{
    int x, y;
};
queue<node> q[2];
int vis[2][1005][1005];
int n, m;

int bfs(int pos){
    int siz=q[pos].size();
    while(siz--){
        node now=q[pos].front(); q[pos].pop();
        for(int k=0; k<4+(pos?0:4); k++){
            int x=now.x+xx[k], y=now.y+yy[k];
            if(x>=1&&x<=n&&y>=1&&y<=m&&!vis[pos][x][y]&&a[x][y]!='#'){
                if(vis[!pos][x][y]){
                    return 1;
                }
                vis[pos][x][y]=1;
                q[pos].push(node{x, y});
            }
        }
    }
    return 0;
}

int main(){
    scanf("%d%d%*c", &n, &m);
    int sx, sy, tx, ty;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            scanf("%c%*c", &a[i][j]);
            if(a[i][j]=='C'){
                sx=i, sy=j;
            }
            if(a[i][j]=='D'){
                tx=i, ty=j;
            }
        }
    }
    int ans=0;
    q[0].push(node{sx, sy}); vis[0][sx][sy]=1;
    q[1].push(node{tx, ty}); vis[1][tx][ty]=1;
    while(!q[0].empty()||!q[1].empty()){
        ans++;
        if(bfs(0)||bfs(1)||bfs(1)){
            printf("YES\n");
            printf("%d\n", ans);
            return 0;
        }
    }
    printf("NO\n");


    return 0;
}