自动搬运

查看原文

来自洛谷，原作者为

	___w **

搬运于2025-08-24 21:34:20，当前版本为作者最后更新于2023-07-04 20:52:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P2130 狂奔的Wzf

题意简述

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

题目分析

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

这一题与其他迷宫题不同之处在于可以走 $2$ 的次方步，但是途径的地方不能是障碍。步长可以用一个数组记录，最多到 $512$。至于判断障碍物，我们可以用前缀和。下文以每一行为例，用数组 $L$ 来分别统计每行的第一列到点 $(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。