题目

题目链接

题解

BFS。

主要的特殊点在于加了很多特殊的情况，逐一判断即可。

注意vis/st标记数组是三维的第一维是行号，第二维是列号，第三维是能量值，表示是否以该能量值到达过该点。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1100;

int n, k, st[N*N][15];
string a[N];
int dir[2][4] = {-1, 1, 0, 0, 0, 0, -1, 1};

struct node {
	int first, second, third; // first：位置，second：能量值，third：步数 
};

int bfs () {
	queue <node> q;
	st[0][0] = 1;
	q.push ({0, 0, 0});
	
	while (q.size()) {
		node t = q.front ();
		int x = t.first / n; // x
		int y = t.first % n; // y
		int m = t.second; // 处于(x,y)位置的能量 
		int d = t.third; // 到达(x,y)的步数 
		q.pop ();
		if (x == n-1 && y == n-1) return d; // 终点 
		for (int i = 0;i < 4;i ++) {
			int tx = x + dir[0][i], ty = y + dir[1][i];
			if (tx < 0 || ty < 0 || tx >= n || ty >= n || a[tx][ty] == '#') continue;
			int tnext = tx*n+ty; // 下一个位置 
			if (a[tx][ty] == '%') { // 如果是能量石 
				if (!st[tnext][k]) st[tnext][k] = 1, q.push ({tnext, k, d+1}); // 如果吃过能量石就不能进入这个if 
				if (!st[tnext][max (0, m-1)]) st[tnext][max (0, m-1)] = 1, q.push ({tnext, max (0, m-1), d+1}); // 如果以m-1的能量值到达过tnext位置，则不会重复 
			} else if (a[tx][ty] == 'X') { // 如果是陷阱 
				if (m && !st[tnext][max (0, m-1)]) st[tnext][max (0, m-1)] = 1, q.push ({tnext, max (0, m-1), d+1}); // 只有有能量才能走 
			} else { // 道路，只要没以m-1的能量到达过就能走 
				if (!st[tnext][max (0, m-1)]) st[tnext][max (0, m-1)] = 1, q.push ({tnext, max (0, m-1), d+1});
			}
		}
	}
	return -1;
}

int main()
{
	cin >> n >> k;
	for (int i = 0;i < n;i ++)
	cin >> a[i];
	
	cout << bfs ();	

	return 0;
}