Nightmare Ⅱ （HDU - 3085，双向 BFS + 模拟）

一.题目链接：

HDU-3085

二.题目大意：

给你一个 n × m 的图，图由以下符号组成.

'.' ：空地

'X' ：墙

'M' ：男

'G' ：女

'Z' ：鬼

规则：

男、女、鬼 都可以向上下左右四个方向走

每秒男的可以走三步，女的走一步，墙不能走.

每秒每个鬼 会分出子鬼占领距离他单位长度 ≤ 2 的方格（包括墙）

若男 || 女 被鬼抓住，则 GG.

问男、女是否能相遇，若能，则输出所需时间，若不能，则输出 -1.

三.分析：

这题就是双向 BFS  + 模拟.

详见代码吧.

四.代码实现：

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-6
#define pi acos(-1.0)
#define ll long long int
using namespace std;

const int M = (int)8e2;

int n, m;

char mp[M + 5][M + 5];
bool vis[2][M + 5][M + 5];

struct node
{
    int x;
    int y;
};

struct node z[2];
struct node s1, s2;

queue <node> q[2];

int Move[4][2] = {
{0, 1}, {0, -1},
{1, 0}, {-1, 0}
};

bool check(node p, int step)
{
    for(int i = 0; i < 2; ++i)
    {
        if((int)abs(p.x - z[i].x) + (int)abs(p.y - z[i].y) <= step * 2)///曼哈顿距离
            return 0;
    }
    return 1;
}

bool bfs(int id, int step)
{
    struct node p, t;
    int len = q[id].size();
    while((len--) > 0)
    {
        p = q[id].front();
        q[id].pop();
        if(!check(p, step))///因为是鬼先走，所以要考虑此时鬼是否会抓住 id
            continue;
        for(int i = 0; i < 4; ++i)
        {
            t = p;
            t.x += Move[i][0];
            t.y += Move[i][1];
            if(t.x < 0 || t.x >= n || t.y < 0 || t.y >= m || vis[id][t.x][t.y] || mp[t.x][t.y] == 'X' || !check(t, step))
                continue;
            vis[id][t.x][t.y] = 1;
            if(vis[!id][t.x][t.y])
                return 1;
            q[id].push(t);
        }
    }
    return 0;
}

int solve()
{
    for(int i = 0; i < 2; ++i)
    {
        while(!q[i].empty())
            q[i].pop();
    }
    memset(vis, 0, sizeof(vis));
    vis[0][s1.x][s1.y] = vis[1][s2.x][s2.y] = 1;
    q[0].push(s1);
    q[1].push(s2);
    int step = 1;
    while(!q[0].empty() || !q[1].empty())
    {
        for(int i = 0; i < 3; ++i)///男 1 秒走 3 步
        {
            if(bfs(0, step))
                return step;
        }
        if(bfs(1, step))///女 1 秒走 1 步
            return step;
        step++;
    }
    return -1;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d %d", &n, &m);
        int cnt = 0;
        for(int i = 0; i < n; ++i)
        {
            ///getchar();
            scanf("%s", mp[i]);///换成注释中的输入 T 爆了！！！
            for(int j = 0; j < m; ++j)
            {
                ///scanf("%c", &mp[i][j])
                if(mp[i][j] == 'M')
                {
                    s1.x = i;
                    s1.y = j;
                }
                else if(mp[i][j] == 'G')
                {
                    s2.x = i;
                    s2.y = j;
                }
                else if(mp[i][j] == 'Z')
                {
                    z[cnt].x = i;
                    z[cnt].y = j;
                    cnt++;
                }
            }
        }
        int ans = solve();
        printf("%d\n", ans);
    }
    return 0;
}