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

思路：BFS, 队列里存储一个包含当前行, 列, 剩余能量的三元组, 用 visited 记录到达当前位置剩余能量的最大值

#include <bits/stdc++.h>
using namespace std;

int main() {
    int r, c, k, start_row, start_col;
    cin >> r >> c >> k;
    vector<string> maze;
    for (int i = 0; i < r; i++) {
        string s;
        cin >> s;
        maze.push_back(s);
        for (int j = 0; j < c; j++) {
            if (s[j] == 'S') {
                start_row = i;
                start_col = j;
            }
        }
    }

    int step = 0;
    vector<vector<int>> visited(r, vector<int>(c, -1));  // remain k when visited[row][col] is reached
    visited[start_row][start_col] = k;
    queue<tuple<int, int, int>> q; // row, col, remain
    q.push({start_row, start_col, k});
    vector<pair<int, int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    
    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            auto [row, col, remain] = q.front();
            q.pop();

            if (maze[row][col] == 'E') {
                cout << step << endl;
                return 0;
            }
            
            for (auto [dr, dc] : directions) {
                int new_row = row + dr;
                int new_col = col + dc;
                if (new_row >= 0 && new_row < r && new_col >= 0 && new_col < c) {
                    int new_remain = remain;  // Create a new variable to store the updated remain value, instead of modifying the original remain variable
                    if (maze[new_row][new_col] == '#') {
                        new_remain--;
                    }

                    if (new_remain >= 0 && visited[new_row][new_col] < new_remain) {
                        visited[new_row][new_col] = new_remain;
                        q.push({new_row, new_col, new_remain});
                    }
                }
            }
        }
        step++;
    }
    cout << -1 << endl;
    return 0;
}