題目描述
小明在玩一款迷宮游戲，在游戲中他要控制自己的角色離開一間由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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/266740.html
標籤：其他