题解：P1455. 走走跳跳

题目

一天 dayz_break 在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由 的格点组成，每个格点只有 种状态，. 和 #，前者表示道路，后者表示围墙。

dayz_break 现在在左上角，他希望走到右下角的位置，他有两种移动方式：

• 如果当前位置是道路，那么可以走到上下左右相邻的道路中。

• 不管当前位置是什么，都可以

  跳跃

  到上下左右四个方向间隔一个格点的位置（不管那个位置是道路还是围墙）。

  • 即可以从 跳跃到 四个位置之一（当然前提条件是这四个位置都在地图内）。

请问 dayz_break 最少使用几次跳跃可以从左上角走到右下角。如果无论如何都无法到达，输出 -1。

题解

方法一：最短路

考虑建模，跳跃边权为一，走路边权为零，根据要求建图跑最短路即可。

关于 SPFA
——他死了

• 蒟蒻使用了 SPFA 在可爱的网格图上直接坠机了，即使使用玄学优化都无力回天。
  相反，堆优化的 DJ 最大的点也只跑了 100ms 左右，这就是 的实力。
• 注意空间，不是 那么点大；

代码：

#include<bits/stdc++.h>
#define LL long long

using namespace std;

const int MAXN = 1005;
const int MAXD = MAXN * MAXN;

const int dx1[] = {2, -2, 0, 0};
const int dy1[] = {0, 0, 2, -2};
const int dx2[] = {1, -1, 0, 0};
const int dy2[] = {0, 0, 1, -1};

LL n, m;
string g[MAXN];

int edgeCount;
int head[MAXD], toNode[MAXD << 4], nextEdge[MAXD << 4];
int edgeWeight[MAXD << 4];

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int dis[MAXD];
bool vis[MAXD];

inline int ind(int x, int y) {
    return (x - 1) * m + y;
}
inline void addEdge(int from, int to, int weight) {
    edgeCount++;
    toNode[edgeCount] = to;
    nextEdge[edgeCount] = head[from];
    edgeWeight[edgeCount] = weight;
    head[from] = edgeCount;
    return;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> g[i];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            if (g[i][j - 1] == '.')
                for (int k = 0; k < 4; ++k) {
                    int xx = i + dx2[k];
                    int yy = j + dy2[k];
                    if (1 <= xx && xx <= n && 1 <= yy && yy <= m && g[xx][yy - 1] == '.') {
                        addEdge(ind(i, j), ind(xx, yy), 0);
                        addEdge(ind(xx, yy), ind(i, j), 0);
                    }
                }
            for (int k = 0; k < 4; ++k) {
                int xx = i + dx1[k];
                int yy = j + dy1[k];
                if (1 <= xx && xx <= n && 1 <= yy && yy <= m) {
                    addEdge(ind(i, j), ind(xx, yy), 1);
                    addEdge(ind(xx, yy), ind(i, j), 1);
                }
            }
        }
    
    memset(dis, 0x3f, sizeof(dis));
    pq.push({0, ind(1, 1)});
    dis[ind(1, 1)] = 0;
    
    while (!pq.empty()) {
        int from = pq.top().second;
        pq.pop();
        
        if (vis[from]) continue;
        vis[from] = true;
        
        for (int i = head[from]; i; i = nextEdge[i]) {
            int to = toNode[i];
            int curDis = dis[from] + edgeWeight[i];
            if (dis[to] > curDis) {
                dis[to] = curDis;
                pq.push({dis[to], to});
            }
        }
    }
    
    if (dis[ind(n, m)] == 0x3f3f3f3f)
        cout << -1, exit(0);
    cout << dis[ind(n, m)];
    return 0;
}

方法二：Bfs

蒟蒻的考场方法，然而想复杂了（想要根据跳跃次数分阶段进行 Bfs），又坠机了；
当时先没注意到后效性，写了个 DP 然后 WA 了，才注意到；
于是想到了这个方法。

注意到 DP 的问题在于后效性，但是为什么 Bfs 没有？而且还没有无限循环访问的问题？
因为我们 Bfs 并不是访问到了就加到队列里，而是他有贡献。
因为 dis 值单调不降，我们用这个入队列方式就可以保证统计完所有最优解的同时不会循环访问。

这个方法显然更快更好，相比起来前者就太大张旗鼓了。

不过网格图跳跃就建图跑最短路是经典方法，不费脑子。

​ —— llttt

代码：

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1005;
const int dx1[] = {2, -2, 0, 0};
const int dy1[] = {0, 0, 2, -2};
const int dx2[] = {1, -1, 0, 0};
const int dy2[] = {0, 0, 1, -1};

int n, m;
string g[MAXN];

queue<int> qx, qy;
int dis[MAXN][MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> g[i];

    memset(dis, 0x3f, sizeof dis);
    dis[1][1] = 0;
    qx.push(1);
    qy.push(1);
    while (!qx.empty()) {
        int fromX = qx.front();
        int fromY = qy.front();
        qx.pop();
        qy.pop();
        if (g[fromX][fromY - 1] == '.')
            for (int i = 0; i < 4; ++i) {
                int xx = fromX + dx2[i];
                int yy = fromY + dy2[i];
                if (1 <= xx && xx <= n && 1 <= yy && yy <= m
                && g[xx][yy - 1] == '.' && dis[xx][yy] > dis[fromX][fromY]) {
                    dis[xx][yy] = dis[fromX][fromY];
                    qx.push(xx);
                    qy.push(yy);
                }
            }
        for (int i = 0; i < 4; ++i) {
            int xx = fromX + dx1[i];
            int yy = fromY + dy1[i];
            int curDis = dis[fromX][fromY] + 1;
            if (1 <= xx && xx <= n && 1 <= yy && yy <= m && dis[xx][yy] > curDis) {
                dis[xx][yy] = curDis;
                qx.push(xx);
                qy.push(yy);
            }
        }
    }

    cout << (dis[n][m] == 0x3f3f3f3f ? -1 : dis[n][m]);
    return 0;
}