自动搬运

查看原文

来自洛谷，原作者为

	Zaku Кто не идет вперед, тот идет назад: стоячего положения нет.

搬运于2025-08-24 22:41:19，当前版本为作者最后更新于2023-03-30 20:50:09，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这题是普通 bfs 的变形题。加了一个道具的操作。

板子相信大家都会敲，那么主要讲一下如何处理无敌道具。

在结构体内新加一个变量 $magic$，表示当前还剩几步的无敌效果。在遍历过程中，如果遇到“X”，并且不剩无敌了，就不能走；如果遇到“%”，$magic$ 变为 $k$。其他情况，并且不为“#”时，把点入队。

这里要加一个剪枝：加一个 int 型的数组 $vis$，入队时需要 vis[x][y] < magic，即如果当前节点已经被访问过，且之前到达该节点时的无敌状态剩余步数比现在要多，则不需要再次访问该节点。因为如果我们之前已经访问过该节点并且使用了更多的无敌步数，那么这条路径一定不是最优解。初始时要赋值为全 $-1$。

代码+详细注释：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
int n, k; 
char g[N][N]; 
int vis[N][N]; // 存储每个格子是否被访问过以及无敌状态剩余步数
struct node{
	int x, y, step, magic;
};

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

int main(){
	cin >> n >> k;
	for (int i = 1; i <= n; i ++ )
		for (int j = 1; j <= n; j ++ )
			cin >> g[i][j];
	memset(vis, -1, sizeof vis);
	queue<node> q;
	vis[1][1] = 0; // 将起点的访问状态设置为0
	q.push({1, 1, 0, 0}); // 将起点入队，并设置其到达该点的步数为0、当前不处于无敌状态
	while (q.size()){
		node t = q.front(); // 取出队头节点
		q.pop();
		if (t.x == n && t.y == n){ // 如果当前节点为终点，则输出最短路长度并结束程序
			cout << t.step;
			return 0;
		}
		for (int i = 0; i < 4; i ++ ){
			int tx = t.x + dx[i];
			int ty = t.y + dy[i];
			if (g[tx][ty] == 'X' && t.magic == 0) // 如果下一步位置是陷阱且当前不处于无敌状态，则跳过该节点
				continue;
			int magic = max(0, t.magic - 1); // 计算当前无敌状态剩余步数
			if (g[tx][ty] == '%') // 如果下一步位置有道具，更新无敌状态剩余步数
				magic = k;
			if (tx >= 1 && tx <= n && ty >= 1 && ty <= n && vis[tx][ty] < magic && g[tx][ty] != '#'){ // 如果下一步位置是合法的可到达位置
				vis[tx][ty] = magic; // 更新访问状态和无敌状态剩余步数
				q.push({tx, ty, t.step + 1, magic}); // 将下一步位置入队，并更新到达该点的步数和无敌状态剩余步数
			}
		}
	}
	cout << -1;
    return 0;
}