M29954 逃离紫罗兰监狱

思路：

• 某一时刻的状态可以描述为 $(x,y,cnt)$，表示位于 $(x,y)$ 且现在已经使用了 $cnt$ 次闪现术。
• 则接下来可以消耗一单位时间移动到 $(x,y,cnt)\to (x+dx,y+dy,cnt+[m{p}_{x+dx,y+dy}=\text{\#}])$，当且仅当：

$$\{\begin{array}{l}|dx|+|dy|=1\\ 0\le x+dx<r,0\le y+dy<c\\ cnt+[m{p}_{x+dx,y+dy}=\text{\#}]\le k\end{array}$$

• 进而不难抽象为一个图论模型：边权均为 $1$ 的分层图单源最短路问题，起点为 $(x_S,y_S,0)$，所有可能的终点为 $(x_E,y_E,\mathrm{\_})$。
• bfs 即可。时间复杂度为 $O(rck)$。

代码：

#include <iostream>
#include <queue>

using namespace std;

struct Node {
	int x;
	int y;
	int cnt;
	int dis;
	
	Node(int _x, int _y, int _cnt, int _dis) : x(_x), y(_y), cnt(_cnt), dis(_dis) {}
};

bool vis[100][100][11];
string mp[100];
queue<Node> q;

void update(int x, int y, int cnt, int dis, int k){
	if (cnt <= k && !vis[x][y][cnt]){
		vis[x][y][cnt] = true;
		q.push(Node(x, y, cnt, dis));
	}
}

int main(){
	int r, c, k, sx = -1, sy;
	cin >> r >> c >> k;
	for (int i = 0; i < r; i++){
		cin >> mp[i];
		if (sx == -1){
			for (int j = 0; j < c; j++){
				if (mp[i][j] == 'S'){
					sx = i;
					sy = j;
					break;
				}
			}
		}
	}
	update(sx, sy, 0, 0, 0);
	while (!q.empty()){
		Node cur = q.front();
		q.pop();
		if (mp[cur.x][cur.y] == 'E'){
			cout << cur.dis;
			return 0;
		}
		for (int i : {-1, 1}){
			int new_x = cur.x + i;
			if (new_x >= 0 && new_x < r) update(new_x, cur.y, cur.cnt + (mp[new_x][cur.y] == '#' ? 1 : 0), cur.dis + 1, k);
		}
		for (int i : {-1, 1}){
			int new_y = cur.y + i;
			if (new_y >= 0 && new_y < c) update(cur.x, new_y, cur.cnt + (mp[cur.x][new_y] == '#' ? 1 : 0), cur.dis + 1, k);
		}
	}
	cout << -1;
	return 0;
}

bfs

#include <iostream>
#include <queue>
#include <vector>

auto main() -> int {
  std::cin.tie(nullptr)->sync_with_stdio(false);

  int R, C, K;
  std::cin >> R >> C >> K;
  std::vector<std::vector<char>> p(R, std::vector<char>(C));

  int sx, sy, dx, dy;
  for (int i = 0; i < R; ++i)
    for (int j = 0; j < C; ++j) {
      std::cin >> p[i][j];
      if (p[i][j] == 'S')
        sx = i, sy = j;
      if (p[i][j] == 'E')
        dx = i, dy = j;
    }

  std::vector<std::vector<std::vector<int>>> visited(
      R, std::vector<std::vector<int>>(C, std::vector<int>(K + 1, -1)));

  std::queue<std::pair<std::pair<int, int>, int>> q;
  q.push({{sx, sy}, K});
  visited[sx][sy][K] = 0;

  int dict[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

  while (!q.empty()) {
    auto [x, y] = q.front().first;
    int k = q.front().second;
    q.pop();

    if (dx == x && dy == y) {
      std::cout << visited[x][y][k] << '\n';
      return 0;
    }

    for (auto &i : dict) {
      int newX = x + i[0], newY = y + i[1];

      if (newX >= 0 && newX < R && newY >= 0 && newY < C) {
        char c = p[newX][newY];
        int next_k = k;
        if (c == '#') {
          if (next_k > 0)
            --next_k;
          else
            continue;
        }

        if (visited[newX][newY][next_k] == -1) {
          q.push({{newX, newY}, next_k});
          visited[newX][newY][next_k] = visited[x][y][k] + 1;
        }
      }
    }
  }

  std::cout << -1 << '\n';
  return 0;
}

共用时30min