EOJ1224 简单迷宫问题

问题描述：一天，sunny 不小心进入了一个迷宫，不仅很难寻找出路，而且有的地方还有怪物，但是 sunny 有足够的能力杀死怪物，但是需要一定的时间，但是 sunny 想早一点走出迷宫，所以请你帮助他计算出最少的时间走出迷宫，输出这个最少时间。
我们规定每走一格需要时间单位 1, 杀死怪物也需要时间 1, 如果不能走到出口，则输出 impossible. 每次走只能是上下左右 4 个方向。
输入：每次首先2个数n, m(0 < n, m <= 200)，代表迷宫的高和宽，然后n行，每行m个字符。
‘S’ 代码你现在所在的位置。
‘T’ 代表迷宫的出口。
‘#’ 代表墙，你是不能走的。
‘X’ 代表怪物。
‘.’ 代表路，可以走。
处理到文件结束。
输出：输出最少的时间走出迷宫。不能走出输出 impossible。

思路：基于广搜的思想，用队列(queue)储存走过的地点。这里我用了自定义结构体队列，x, y表示地点的坐标，n表示到这一步已走的步数，b用来记录这个点是否为怪物(若为怪物，则令b为1并将这个地点坐标入队，准备将队列头的结构体的子状态(地点)入队前先判断其b是否为1，若为1则将其改为0并将其自身入队，若为0则将其子状态入队，之后都要将队列头出队)。若遇到子状态为目标状态(出口坐标)则返回当前步数加1；若最后队列为空时仍未到达出口，则返回0。

#include 

using namespace std;

struct point1
{
    int x;
    int y;
    int n;
    bool b;
};

int bfs(vector>, int, int);

int main()
{
    int n, m, sx, sy;

    while (cin >> n >> m)
    {
        vector> a;
        a.resize(n);
        for (int i{}; i < n; i++) {
            for (int j{}; j < m; j++) {
                char tmp;
                cin >> tmp;
                a[i].push_back(tmp);
                if (tmp == 'S') {
                    sx = i;
                    sy = j;
                }
            }
        }
        int can = bfs(a, sx, sy);
        if (can) {
            cout << can;
        } else {
            cout << "impossible";
        }
        cout << endl;
    }

    return 0;
}

int bfs(vector> a, int x, int y)
{
    queue q;
    for (q.push({x, y, 0, 0}); !(q.empty()); q.pop()) { // 初始化时先将起点入队，每次循环都要将当前队列头出队，若队列为空则退出循环并返回0
        if (q.front().b) {  // 若当前队列头的坐标原本为怪物
            q.push({q.front().x, q.front().y, q.front().n, false}); // 则将其b改为0并入队加入下一轮循环
            continue;
        }
        if ((q.front().x + 1) < a.size() && a[q.front().x + 1][q.front().y] == '.') {
            a[q.front().x + 1][q.front().y] = '#';  // 每次入队时将这个地点改为墙
            q.push({q.front().x + 1, q.front().y, q.front().n + 1, false}); // 将子状态入队
        } else if ((q.front().x + 1) < a.size() && a[q.front().x + 1][q.front().y] == 'X') {
            a[q.front().x + 1][q.front().y] = '#';
            q.push({q.front().x + 1, q.front().y, q.front().n + 2, true});
        } else if ((q.front().x + 1) < a.size() && a[q.front().x + 1][q.front().y] == 'T') {    // 若子状态为出口
            return q.front().n + 1; // 返回当前步数加1
        }
        if ((q.front().x - 1) >= 0 && a[q.front().x - 1][q.front().y] == '.') {
            a[q.front().x - 1][q.front().y] = '#';
            q.push({q.front().x - 1, q.front().y, q.front().n + 1, false});
        } else if ((q.front().x - 1) >= 0 && a[q.front().x - 1][q.front().y] == 'X') {
            a[q.front().x - 1][q.front().y] = '#';
            q.push({q.front().x - 1, q.front().y, q.front().n + 2, true});
        } else if ((q.front().x - 1) >= 0 && a[q.front().x - 1][q.front().y] == 'T') {
            return q.front().n + 1;
        }
        if ((q.front().y + 1) < a[0].size() && a[q.front().x][q.front().y + 1] == '.') {
            a[q.front().x][q.front().y + 1] = '#';
            q.push({q.front().x, q.front().y + 1, q.front().n + 1, false});
        } else if ((q.front().y + 1) < a[0].size() && a[q.front().x][q.front().y + 1] == 'X') {
            a[q.front().x][q.front().y + 1] = '#';
            q.push({q.front().x, q.front().y + 1, q.front().n + 2, true});
        } else if ((q.front().y + 1) < a[0].size() && a[q.front().x][q.front().y + 1] == 'T') {
            return q.front().n + 1;
        }
        if ((q.front().y - 1) >= 0 && a[q.front().x][q.front().y - 1] == '.') {
            a[q.front().x][q.front().y - 1] = '#';
            q.push({q.front().x, q.front().y - 1, q.front().n + 1, false});
        } else if ((q.front().y - 1) >= 0 && a[q.front().x][q.front().y - 1] == 'X') {
            a[q.front().x][q.front().y - 1] = '#';
            q.push({q.front().x, q.front().y - 1, q.front().n + 2, true});
        } else if ((q.front().y - 1) >= 0 && a[q.front().x][q.front().y - 1] == 'T') {
            return q.front().n + 1;
        }
    }
    return 0;
}