題目描述
小明在玩一款迷宮游戲，在游戲中他要控制自己的角色離開一間由NxN個格子組成的2D迷宮。
小明的起始位置在左上角，他需要到達右下角的格子才能離開迷宮。
每一步，他可以移動到上下左右相鄰的格子中（前提是目標格子可以經過）。
迷宮中有些格子小明可以經過，我們用’.‘表示；
有些格子是墻壁，小明不能經過，我們用’#‘表示。
此外，有些格子上有陷阱，我們用’X’表示。除非小明處于無敵狀態，否則不能經過。
有些格子上有無敵道具，我們用’%‘表示。
當小明第一次到達該格子時，自動獲得無敵狀態，無敵狀態會持續K步。
之后如果再次到達該格子不會獲得無敵狀態了。
處于無敵狀態時，可以經過有陷阱的格子，但是不會拆除/毀壞陷阱，即陷阱仍會阻止沒有無敵狀態的角色經過。
給定迷宮，請你計算小明最少經過幾步可以離開迷宮
輸入
輸入包含多組測試數據，對于每組測試數據：
第一行包含兩個整數N和K。 (1 <= N <= 1000 1 <= K <= 10)
以下N行包含一個NxN的矩陣。矩陣保證左上角和右下角是’.’。
輸出
對于每組測試數據輸出一行包含一個整數表示答案。
如果小明不能離開迷宮，輸出-1。
樣例輸入

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

樣例輸出

10 12

解題思路：
挺明顯的一個bfs題目，但是某個點不能單純的走過就不能走了，因為有另外一個元素k。而且k很小。所以我們就用一個三維數組標記，如果某個點在無敵狀態為k時已經走過了，就不能再走了。剩下的就是在每一種狀態時的判斷了。

關鍵點:在于走過的點可能還會重復走（比如去另一個方向獲得無敵值再回來），所以用傳統的bfs絕對不行，因此需要設一個三維數組st[a][b][c] 標記點(a,b)在無敵值為c的時候是否已經走過，走過的話就不再走了。只有當去獲得無敵值時才會重復走。

代碼如下：

#include <iostream> #include <cstring> #include <queue> using namespace std; const int N = 1010; char g[N][N]; bool st[N][N][12]; //st[a][b][k]表示(a,b)點在無敵值為k的時候是否走過，如果已經走過了那么以后就不會再重復走。再走的話說明是獲取到了無敵值 //用這種三維數組標記巧妙的避免了兩個點之間的死循環無限走 int n, k;int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};struct node {int x, y, k, step; };int bfs() {queue<node>q;memset(st, 0, sizeof(st));q.push({1, 1, 0, 0});st[1][1][0] = true;while (q.size()) {node t = q.front();q.pop();if (t.x == n && t.y == n)return t.step;for (int i = 0; i < 4; i++) {int xx = t.x + dx[i], yy = t.y + dy[i];if (xx >= 1 && xx <= n && yy >= 1 && yy <= n && g[xx][yy] != '#') {if (g[xx][yy] == '%' && st[xx][yy][t.k] == 0) {g[xx][yy] = '.';st[xx][yy][k] = true;q.push({xx, yy, k, t.step + 1});//這里只要第一次遇到無敵道具，就會重置無敵狀態，所以是k，不是t.k}if (g[xx][yy] == 'X' && t.k && st[xx][yy][t.k - 1] == 0) {st[xx][yy][t.k - 1] = true;q.push({xx, yy, t.k - 1, t.step + 1});}if (g[xx][yy] == '.' && t.k && st[xx][yy][t.k - 1] == 0) {st[xx][yy][t.k - 1] = true;q.push({xx, yy, t.k - 1, t.step + 1});}if (g[xx][yy] == '.' && t.k == 0 && st[xx][yy][0] == 0) {st[xx][yy][0] = true;q.push({xx, yy, 0, t.step + 1});}}}}return -1; }int main() {while (cin >> n >> k) {for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)cin >> g[i][j];//這道題要用雙層循環才可以AC，//但我不知道為什么用一層循環不行，//所以做題的時候推薦都用雙層循環讀入吧cout << bfs() << endl;}return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的[蓝桥杯2018决赛]迷宫与陷阱的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。