P2130 狂奔的Wzf

· · 题解

P2130 狂奔的Wzf

题意简述

从 (1,1) 开始，每秒可以向上下左右某一方向走 2 的次方步，问至少多久可以到达作业。

题目分析

注意点 1<n,m<1000，我们可以考虑搜索。因为题目要求的是最短耗时，所以用 bfs 比较合适，第一次到达终点的即为答案。

这一题与其他迷宫题不同之处在于可以走 2 的次方步，但是途径的地方不能是障碍。步长可以用一个数组记录，最多到 512。至于判断障碍物，我们可以用前缀和。下文以每一行为例，用数组 L 来分别统计每行的第一列到点 (i,j) 的障碍数有多少个。有公式:

L_{i,j}=L_{i,j-1}+P_{i,j}

其中 P_{i,j} 为点 (i,j) 上是否有障碍物。有，则为 1；没有，则为 0。

有了前缀和，我们则可以判断点 (x,y) 到点 (x,z) 上是否有障碍物。若 L_{x,z}-L_{x,y}=0，则路径上没有障碍物；否则没有障碍物。每一列判断也同理。

其他则就同普通的迷宫一般了，具体看代码。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1000;
struct node {
    int x, y, t;
} ;
int n, m, h[N][N], l[N][N];
int d[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int p[10] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
bool vis[N][N];
char c[N][N];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            cin >> c[i][j];
            h[i][j] = h[i-1][j]+(c[i][j] == 'X');
            l[i][j] = l[i][j-1]+(c[i][j] == 'X');
        }
    queue <node> q;
    q.push((node){1, 1, 0}), vis[1][1] = 1;
    while (!q.empty()) {
        node now = q.front(); q.pop();
        if (c[now.x][now.y] == '#') {
            cout << now.t;
            return 0;
        }
        for (int i = 0; i < 4; ++i)
            for (int j = 0; j < 10; ++j) {
                int x = now.x+d[i][0]*p[j], y = now.y+d[i][1]*p[j];
                if (x < 1 || x > n || y < 1 || y > m || vis[x][y]) continue;
                if (c[x][y] == 'X') break;
                if (d[i][0] && h[x][y]-h[now.x][now.y]) break;
                if (d[i][1] && l[x][y]-l[now.x][now.y]) break;
                q.push((node){x, y, now.t+1}), vis[x][y] = 1;
            }
    }
    cout << -1;
    return 0;
}

record。