蓝桥杯历届试题|第九届蓝桥杯（国赛）——迷宫与陷阱蓝桥杯历届试题|BFS

问题描述
小明在玩一款迷宫游戏，在游戏中他要控制自己的角色离开一间由 N x N 个格子组成的2D迷宫。
小明的起始位置在左上角，他需要到达右下角的格子才能离开迷宫，每一步，他可以移动到上下左右相邻的格子中。
迷宫中有些格子小明可以经过，我们用 '.' 表示；有些格子是墙壁，小明不能经过，我们用 '#' 表示。
此外，有些格子上有陷阱，我们用 'X' 表示，除非小明处于无敌状态，否则不能经过；有些格子上有无敌道具，我们用 '%' 表示。
当小明第一次到达该格子时，自动获得无敌状态，无敌状态会持续 K 步，之后如果再次到达该格子不会获得无敌状态了。
处于无敌状态时，可以经过有陷阱的格子，但是不会拆除/毁坏陷阱，即陷阱仍会阻止没有无敌状态的角色经过。
给定迷宫，请你计算小明最少经过几步可以离开迷宫？
输入格式
第一行包含两个整数 N 和 K。
以下 N 行包含一个 N x N 的矩阵（矩阵保证左上角和右下角是 ‘.’）。
输出格式
一个整数表示答案。如果小明不能离开迷宫，输出 -1。
【蓝桥杯历届试题|第九届蓝桥杯（国赛）——迷宫与陷阱】样例输入1

5 3 ...XX ##%#. ...#. .###. .....

样例输出1
10
样例输入2

5 1 ...XX ##%#. ...#. .###. .....

样例输出2
12
数据范围
1 ≤ N ≤ 1000
1 ≤ K ≤ 10
题解
BFS：
st[x][y][k]：走到 (x, y)，还有 k 步无敌状态。

#include #include #include using namespace std; const int N = 1010; int n, k; char g[N][N]; bool st[N][N][15]; int dx[4] = {0, 1, 0, -1}; int dy[4] = {-1, 0, 1, 0}; struct node { int x, y, k, cnt; node(int a, int b, int c, int d)// 构造函数 { x = a, y = b, k = c, cnt = d; } }; int bfs() { queue q; st[1][1][0] = true; q.push(node(1, 1, 0, 0)); while(q.size()) { node t = q.front(); q.pop(); if(t.x == n && t.y == n) return t.cnt; for (int i = 0; i < 4; i ++) { int a = t.x + dx[i], b = t.y + dy[i]; if(a < 1 || a > n || b < 1 || b > n ||g[a][b] == '#') continue; if(g[a][b] == '%' && !st[a][b][k]) { g[a][b] = '.'; st[a][b][k] = true; q.push(node(a, b, k, t.cnt + 1)); } else { if(g[a][b] == 'X' && t.k && !st[a][b][t.k - 1]) { st[a][b][t.k - 1] = true; q.push(node(a, b, t.k - 1, t.cnt + 1)); }if(g[a][b] == '.' && t.k && !st[a][b][t.k - 1]) { st[a][b][t.k - 1] = true; q.push(node(a, b, t.k - 1, t.cnt + 1)); }if(g[a][b] == '.' && !t.k && !st[a][b][0]) { st[a][b][0] = true; q.push(node(a, b, 0, t.cnt + 1)); } } } } return -1; }int main() { cin >> n >> k; for (int i = 1; i <= n; i ++) cin >> g[i] + 1; cout << bfs() << endl; return 0; }