題目描述
小明在玩一款迷宮游戲，在游戲中他要控制自己的角色離開一間由NxN個格子組成的2D迷宮。
小明的起始位置在左上角，他需要到達(dá)右下角的格子才能離開迷宮。
每一步，他可以移動到上下左右相鄰的格子中（前提是目標(biāo)格子可以經(jīng)過）。
迷宮中有些格子小明可以經(jīng)過，我們用’.‘表示；
有些格子是墻壁，小明不能經(jīng)過，我們用’#'表示。
此外，有些格子上有陷阱，我們用’X’表示。除非小明處于無敵狀態(tài)，否則不能經(jīng)過。

有些格子上有無敵道具，我們用’%'表示。
當(dāng)小明第一次到達(dá)該格子時，自動獲得無敵狀態(tài)，無敵狀態(tài)會持續(xù)K步。
之后如果再次到達(dá)該格子不會獲得無敵狀態(tài)了。

處于無敵狀態(tài)時，可以經(jīng)過有陷阱的格子，但是不會拆除/毀壞陷阱，即陷阱仍會阻止沒有無敵狀態(tài)的角色經(jīng)過。

給定迷宮，請你計算小明最少經(jīng)過幾步可以離開迷宮
輸入
第一行包含兩個整數(shù)N和K。 (1 <= N <= 1000 1 <= K <= 10)
以下N行包含一個NxN的矩陣。
矩陣保證左上角和右下角是’.’。
輸出
一個整數(shù)表示答案。如果小明不能離開迷宮，輸出-1。
樣例輸入
5 3
…XX
##%#.
…#.
.###.
…
樣例輸出
10
思路：挺明顯的一個bfs題目，但是某個點不能單純的走過就不能走了，因為有另外一個元素k。而且k很小。所以我們就用一個三維數(shù)組標(biāo)記，如果某個點在無敵狀態(tài)為k時已經(jīng)走過了，就不能再走了。剩下的就是在每一種狀態(tài)時的判斷了。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e3+100; struct node{int x,y,k,val;node(int a,int b,int c,int v){x=a,y=b,k=c,val=v;} }; int d[][2]={{1,0},{0,1},{0,-1},{-1,0}}; char s[maxx][maxx]; int vis[maxx][maxx][11]; int n,k;inline int bfs() {queue<node> q;vis[0][0][0]=1;q.push(node(0,0,0,0));while(q.size()){node u=q.front();q.pop();if(u.x==n-1&&u.y==n-1) return u.val;for(int i=0;i<4;i++){int tx=u.x+d[i][0];int ty=u.y+d[i][1];if(tx<0||ty<0||tx>=n||ty>=n||s[tx][ty]=='#') continue;if(s[tx][ty]=='%'&&vis[tx][ty][k]==0){vis[tx][ty][k]=1;q.push(node(tx,ty,k,u.val+1));}else {if(s[tx][ty]=='X'&&u.k&&vis[tx][ty][u.k-1]==0){vis[tx][ty][u.k-1]=1;q.push(node(tx,ty,u.k-1,u.val+1));}else if(s[tx][ty]=='.'&&u.k&&vis[tx][ty][u.k-1]==0){vis[tx][ty][u.k-1]=1;q.push(node(tx,ty,u.k-1,u.val+1));}else if(s[tx][ty]=='.'&&u.k==0&&vis[tx][ty][0]==0){vis[tx][ty][0]=1;q.push(node(tx,ty,0,u.val+1));}}}}return -1; } int main() {scanf("%d%d",&n,&k);memset(vis,0,sizeof(vis));for(int i=0;i<n;i++) scanf("%s",s[i]);int ans=bfs();if(ans==-1) printf("-1\n");else printf("%d\n",ans);return 0; }

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的[蓝桥杯][2018年第九届真题]迷宫与陷阱（三维数组标记BFS）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。