题解：AT_abc387_d [ABC387D] Snaky Walk

· · 题解

题目传送门

Atcoder 传送门

题目大意

你在一个 n\times m 的网格中，起点为标有 S 的网格，你需要走到标有 G 的网格。

对于每次移动：

我们发现，这又是经典的走迷宫问题，要求指定条件下的最短路径。

首先想到 dfs 算法，每次移动有 4 种方式，时间复杂度 \mathcal{O}(4^{n\times m})，明显无法通过（n, m\le1000）。

接着就会想到 bfs 算法。第一次移动有两种选择（左右、上下），只需要做两次 bfs 即可：

最高时间复杂度：\mathcal{O}(n\times m)，可以通过。

提示：千万要打标记喵~

代码实现

#include <bits/stdc++.h>
using namespace std;

const int inf = 0x7fffffff;

int n, m, sx, sy, fx, fy, ans = -1;
int mx[] = {0, 0, 0, 1, -1}; // 打四个方向的表
int my[] = {0, 1, -1, 0, 0};
char s[1002][1002];
bool vis[1002][1002];

struct S {
    int x, y, ans;
    bool step;// 0: up/down, 1: left/right
};

deque <S> q;

int main() {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) for (int j = 1;j <= m;j++) {
        cin >> s[i][j];
        if (s[i][j] == 'S') sx = i, sy = j; // 预先找到 'S' 和 'G'（起点和终点）
        if (s[i][j] == 'G') fx = i, fy = j;
    }
    q.push_back({sx, sy, 0, 0}); // 在起始点可以左右走（假设前一次上下走）
    while (!q.empty()) {
        S a = q.front();
        q.pop_front();
        if (vis[a.x][a.y]) continue; // 判断是否访问，访问过就跳过本次循环
        vis[a.x][a.y] = 1; // 一定要打标记！！！
        if (a.x == fx && a.y == fy) {ans = a.ans;break;} // 搜到终点直接退出
        for (int i = 1;i <= 4;i++) { // 枚举四个方向
            int nx = a.x + mx[i], ny = a.y + my[i]; // 计算目标位置
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue; // 边界条件记得判断
            if (s[nx][ny] == '#') continue; // 判断是否为墙
            if (a.step == 0 && (i == 3 || i == 4)) continue; // 上一次上/下走，且这次仍然上/下走，不符合题意
            if (a.step == 1 && (i == 1 || i == 2)) continue; // 上一次左/右走，且这次仍然左/右走，不符合题意
            q.push_back({nx, ny, a.ans + 1, bool(i == 1 || i == 2 ? 1 : 0)}); // 添加这种状态
        }
//        cout << a.x << " " << a.y << endl;
    }
    while (!q.empty()) q.pop_front(); // 记得清空队列
    q.push_back({sx, sy, 0, 1}); // 这里的最后一个数不一样
    memset(vis, 0, sizeof(vis)); // 清空标记
    while (!q.empty()) { // 第二遍 bfs 直接复制第一次的
        S a = q.front();
        q.pop_front();
        if (vis[a.x][a.y]) continue;
        vis[a.x][a.y] = 1;
        if (a.x == fx && a.y == fy) {ans = min((ans == -1 ? inf : ans), a.ans);break;}
        for (int i = 1;i <= 4;i++) {
            int nx = a.x + mx[i], ny = a.y + my[i];
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
            if (s[nx][ny] == '#') continue;
            if (a.step == 0 && (i == 3 || i == 4)) continue;
            if (a.step == 1 && (i == 1 || i == 2)) continue;
            q.push_back({nx, ny, a.ans + 1, bool(i == 1 || i == 2 ? 1 : 0)});
        }
    }
    cout << ans << endl;
    return 0;
}