题解：AT_abc420_d [ABC420D] Toggle Maze

· · 题解

ABC 420 D - Toggle Maze

题目大意

有大小为 N \times M 的矩形地图，其中包含障碍物、打开的门、关闭的门、开关。

其中障碍物及关闭的门是无法通行的，但每次经过开关时，所有打开的门会关上，而关闭的门会打开。

每次可以向上下左右四个方向移动，给定原始地图及起点、终点，需要求出到达终点的最少步数，或报告无解。

题目标签

题解

本题的关键点在于处理门和开关。

在原地图基础上进行拆点建图，新增一维状态表示目前经过开关次数的奇偶性。

这样，在搜索的过程中就可以实时知道并维护门的开关状态。在这张新图上进行BFS即可求出最少步数。

时间复杂度：O(N \cdot M)。

额外空间复杂度：O(N \cdot M)。

参考代码

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

const int dx[4] = {0, 0, -1, 1};
const int dy[4] = {-1, 1, 0, 0};

int n, m;
string s[500];
int res[500][500][2];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> s[i];
    memset(res, 0x3f, sizeof(res));
    queue<tuple<int, int, int>> q;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (s[i][j] == 'S')
                res[i][j][0] = 0, q.emplace(i, j, 0);
    while (!q.empty()) {
        const auto [x, y, flag] = q.front();
        q.pop();
        if (s[x][y] == 'G') {
            cout << res[x][y][flag] << '\n';
            return 0;
        }
        for (int i = 0; i < 4; i++) {
            const int X = x + dx[i], Y = y + dy[i];
            if (0 <= X && X < n &&
                0 <= Y && Y < m &&
                s[X][Y] != '#' &&
                (s[X][Y] != 'o' || flag == 0) &&
                (s[X][Y] != 'x' || flag == 1) &&
                res[X][Y][flag ^ (s[X][Y] == '?')] == INF)
                    res[X][Y][flag ^ (s[X][Y] == '?')] = res[x][y][flag] + 1,
                    q.emplace(X, Y, flag ^ (s[X][Y] == '?'));
        }
    }
    cout << -1 << '\n';
    return 0;
}

整场比赛题解：AtCoder Beginner Contest 420 题解 (A~E & G)。