HDU-3085双向搜索+曼哈顿距离

个人觉得这道题真的不错，以下是题目链接
VJ HDU
这道题就是其实是说有两个原点(男孩和女孩）和一个幽灵，幽灵可以穿墙也就是说幽灵在该地图上畅通无阻。
题目描述的幽灵的行动其实就是一个曼哈顿距离。
以一个简单的例子来介绍曼哈顿距离e.g. 打印一个菱形。
比如说以点(r, c))中心打印一个边长为length的菱形以1代表格点。
以下是代码

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    const int maxx = 10;
    int len = 3;  //打印边长为3的菱形
    int r = 5, c = 5;  // 中心为(5, 5)
    string query;
    while (true) {
        cout << "Want to cintunue?[Y/N]" << endl;
        cin >> query;
        if ("N" == query) 
            break;
        for (int i = 1; i <= maxx; ++i) {
            for (int j = 1; j <= maxx; ++j) {
                if (abs(i - r) + abs(j - c) <= len)
                //abs(i - r)距离中心的横坐标 
                //abs(j - c)距离中心的纵坐标
                    cout << 1 << " ";
                else 
                    cout << 0 << " ";
            }
            cout << endl;
        }
    }
    return 0;
}

题意：
不管是幽灵还是人都可以走四个方向
<1> Z(幽灵)依次可以走两步以内，可穿墙
<2>M可以走0, 1, 2, 3步
<3>G可以走0, 1步

#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <climits>
#include <set>
#include <queue>
#include <cmath>
using namespace std;
const int maxx = 805;
char maze[maxx][maxx];
int n, m;
int vis[2][maxx][maxx];
struct node {
    int r, c;

    node(int r =  0, int c = 0) : r(r), c(c) {}
}ghost[2];
queue<node> q[2];
const int dir[][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
bool caught(int r, int c, int time) {
    if (abs(ghost[0].r - r) + abs(ghost[0].c - c) <= 2 * time) return true;
    return abs(ghost[1].r - r) + abs(ghost[1].c - c) <= 2 * time;
    //用曼哈顿距离来表示能不能被幽灵抓到，因为只有两个幽灵就是说以这两个幽灵的坐标为中心的曼哈顿距离
}

inline bool check(int r, int c) {
    return r >= 0 && c >= 0 && r < n && c < m;
}

bool bfs(int id, int time) {
    int count = q[id].size(); //记录下上一次状态的数量
    while (count--) {
        node src = q[id].front(); q[id].pop();
        if (caught(src.r, src.c, time)) continue;
        //因为题目中说幽灵先移动，所以如果有状态被幽灵碰到就属于失效状态
        for (int i = 0; i < 4; ++i) {
            int r = src.r + dir[i][0], c = src.c + dir[i][1];
            if (check(r, c) && 'X' != maze[r][c] && !vis[id][r][c] && !caught(r, c, time)) {
                q[id].push(node(r, c));
                vis[id][r][c] = 1;
                if (vis[!id][r][c]) { // 找到结果
                    return true;
                }
            }
        }
    }
    return false; //不要忘记返回false否则默认返回true
}

int solve() {
    int time = 0;
    while (!q[0].empty() || !q[1].empty()) {
        ++time;
        for (int i = 1; i <= 3; ++i) {
            if (bfs(0, time)) return time;
        }
        if (bfs(1, time)) return time;
    }
    return -1;
}

int main() {
    int t; scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        memset(vis, 0, sizeof vis);
        while (!q[0].empty()) q[0].pop();
        while (!q[1].empty()) q[1].pop();
        int tmp = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%s", maze[i]);
            for (int j = 0; j < m; ++j) {
                if ('Z' == maze[i][j]) {
                    ghost[tmp].r = i;
                    ghost[tmp++].c = j;
                    maze[i][j] = 'X'; //将幽灵的位置变成强便于处理
                }
                if ('M' == maze[i][j]) {
                    q[0].push(node(i, j));
                    vis[0][i][j] = 1;
                }
                if ('G' == maze[i][j]) {
                    q[1].push(node(i, j));
                    vis[1][i][j] = 1;
                }
            }
        }
        printf("%d\n", solve());
    }
    return 0;
}