F - Nightmare Ⅱ HDU - 3085——双向BFS

朱雀 2022-06-14 03:28 135阅读 0赞

Think:  
1知识学习感悟:感觉双向BFS就是你从两个点开始同时进行队列思想的扩展，一旦范围重合说明相遇，其实更像是一种多点同时开始跑，将一些实现可能性相对较弱的点延迟搜索，给我一种逐渐向A\*搜索这种启发式搜索实现的估价思想  
2双向BFS理解参考：双向bfs就是用两个队列，一个队列保存从起点开始的状态，另一个保存从终点开始向前搜索的状态，双向bfs主要是区分每个格子是从起点开始搜索到的还是从终点开始搜索到的.每个经过的格子结点保存到达该格子经过的步数，这样两边要是相交了相加就是结果  
[参考博客\[BFS、双向BFS和A\*\]][BFS_BFS_A]

[vjudge题目链接][vjudge]

F - Nightmare Ⅱ HDU - 3085
         Last night, little erriyue had a horrible nightmare. He dreamed that he and his girl friend were trapped in a big maze separately. More terribly, there are two ghosts in the maze. They will kill the people. Now little erriyue wants to know if he could find his girl friend before the ghosts find them.
        You may suppose that little erriyue and his girl friend can move in 4 directions. In each second, little erriyue can move 3 steps and his girl friend can move 1 step. The ghosts are evil, every second they will divide into several parts to occupy the grids within 2 steps to them until they occupy the whole maze. You can suppose that at every second the ghosts divide firstly then the little erriyue and his girl friend start to move, and if little erriyue or his girl friend arrive at a grid with a ghost, they will die.
        Note: the new ghosts also can devide as the original ghost.
    Input
        The input starts with an integer T, means the number of test cases.
        Each test case starts with a line contains two integers n and m, means the size of the maze. (1<n, m<800)
        The next n lines describe the maze. Each line contains m characters. The characters may be:
        ‘.’ denotes an empty place, all can walk on.
        ‘X’ denotes a wall, only people can’t walk on.
        ‘M’ denotes little erriyue
        ‘G’ denotes the girl friend.
        ‘Z’ denotes the ghosts.
        It is guaranteed that will contain exactly one letter M, one letter G and two letters Z.
    Output
        Output a single integer S in one line, denotes erriyue and his girlfriend will meet in the minimum time S if they can meet successfully, or output -1 denotes they failed to meet.
    Sample Input
    
        3
        5 6
        XXXXXX
        XZ..ZX
        XXXXXX
        M.G...
        ......
        5 6
        XXXXXX
        XZZ..X
        XXXXXX
        M.....
        ..G...
    
        10 10
        ..........
        ..X.......
        ..M.X...X.
        X.........
        .X..X.X.X.
        .........X
        ..XX....X.
        X....G...X
        ...ZX.X...
        ...Z..X..X
    
    Sample Output
    
        1
        1
        -1

以下为Accepted代码

#include <bits/stdc++.h>
    
    using namespace std;
    
    char str[804][804];/*地图标记*/
    int n, m, step;
    int jk[4][2] = {
       {
       0,1},{
       1,0},{
       0,-1},{-1,0}};/*移动方向*/
    
    struct node {
        int x;
        int y;
    }gg, mm, zz[4];
    /*gg表示G的位置记录，mm表示M的位置记录，zz[4]表示鬼魂的位置记录*/
    
    queue<node> q[2], qt;
    
    int solve();/*双向BFS*/
    bool BFS(int mark, int num, char start, char endd);
    /*mark表示M或G的队列标记, num表示mark可移动的最大位移，start表示谁来走，endd表示要到谁*/
    bool isok(node t);/*判断t位置可否到达*/
    
    int main(){
        int T, k, i, j;
        scanf("%d", &T);
        while(T--){
            scanf("%d %d", &n, &m);
            memset(str, 'X', sizeof(str));/*初始化所有位置为墙，之后的操作可直接在地图上标记走过的结点*/
            k = 0;
            for(i = 1; i <= n; i++){
                scanf("%s", str[i]+1);/*地图录入*/
                for(j = 1; j <= m; j++){
                    if(str[i][j] == 'M') mm.x = i, mm.y = j;/*寻找并记录M的位置*/
                    if(str[i][j] == 'G') gg.x = i, gg.y = j;/*寻找并记录G的位置*/
                    if(str[i][j] == 'Z') zz[k].x = i, zz[k].y = j, k++;/*寻找并记录鬼的位置*/
                }
            }
            printf("%d\n", solve());/*双向BFS直接返回最短时间或不可达判断*/
        }
    }
    int solve(){
        step = 0;/*最短时间记录变量初始化*/
        while(!q[0].empty()) q[0].pop();/*队列初始化*/
        while(!q[1].empty()) q[1].pop();/*队列初始化*/
        while(!qt.empty()) qt.pop();/*队列初始化*/
    
        q[0].push(mm), q[1].push(gg);/*M结点和G结点入队*/
        while(!q[0].empty() && !q[1].empty()){
       /*双向BFS展开*/
            step++;/*鬼先移动*/
            bool flag1 = BFS(0, 3, 'M', 'G');/*结点可达性相遇则返回true*/
            bool flag2 = BFS(1, 1, 'G', 'M');/*结点可达性相遇则返回true*/
            if(flag1 || flag2) return step;/*安全相遇返回最短时间*/
        }
        return -1;/*不可达即无法安全相遇*/
    }
    bool BFS(int mark, int num, char start, char endd){
       /*BFS展开进行结点扩展*/
        node a, b;
        qt = q[mark];/*对mark标记的队列进行展开*/
        for(int i = 0; i < num; i++){
            while(!qt.empty()){
       /*队列可达性模拟*/
                a = qt.front(), qt.pop(), q[mark].pop();
                if(!isok(a)) continue;
                for(int i = 0; i < 4; i++){
                    b = a;
                    b.x += jk[i][0];
                    b.y += jk[i][1];
                    if(!isok(b) || str[b.x][b.y] == start)/*判断当前结点可否到达*/
                        continue;
                    if(str[b.x][b.y] == endd)/*其中一个人到达了另一个人曾经到达的结点，即可成功相遇，返回true*/
                         return true;
                    str[b.x][b.y] = start;/*在地图上标记当前结点已经经过*/
                    q[mark].push(b);/*可达性结点入队*/
                }
            }
            qt = q[mark];/*新状态进行展开*/
        }
        return false;/*返回false表示当前并未成功相遇*/
    }
    bool isok(node t){
       /*判断当前结点可否达到*/
        if(t.x < 1 || t.x > n || t.y < 1 || t.y > m)/*判断当前结点是否越界*/
            return false;
        for(int i = 0; i < 2; i++){
            if(abs(t.x-zz[i].x)+abs(t.y-zz[i].y) <= 2*step || str[t.x][t.y] == 'X')/*判断当前结点是否鬼已覆盖*/
                return false;
        }
        return true;/*返回true表示当前结点可以到达*/
    }

[BFS_BFS_A]: http://m.blog.csdn.net/article/details?id=41121517
[vjudge]: https://cn.vjudge.net/contest/161869#problem/F