題干：

This story happened on the background of Star Trek.?

Spock, the deputy captain of Starship Enterprise, fell into Klingon’s trick and was held as prisoner on their mother planet Qo’noS.?

The captain of Enterprise, James T. Kirk, had to fly to Qo’noS to rescue his deputy. Fortunately, he stole a map of the maze where Spock was put in exactly.?

The maze is a rectangle, which has n rows vertically and m columns horizontally, in another words, that it is divided into n*m locations. An ordered pair (Row No., Column No.) represents a location in the maze. Kirk moves from current location to next costs 1 second. And he is able to move to next location if and only if:?

Next location is adjacent to current Kirk’s location on up or down or left or right(4 directions)?
Open door is passable, but locked door is not.?
Kirk cannot pass a wall?

There are p types of doors which are locked by default. A key is only capable of opening the same type of doors. Kirk has to get the key before opening corresponding doors, which wastes little time.?

Initial location of Kirk was (1, 1) while Spock was on location of (n, m). Your task is to help Kirk find Spock as soon as possible.

Input

The input contains many test cases.?

Each test case consists of several lines. Three integers are in the first line, which represent n, m and p respectively (1<= n, m <=50, 0<= p <=10).?
Only one integer k is listed in the second line, means the sum number of gates and walls, (0<= k <=500).?

There are 5 integers in the following k lines, represents x?i1, y?i1, x?i2, y?i2, gi; when g?i?>=1, represents there is a gate of type gi between location (x?i1, y?i1) and (x?i2, y?i2); when g?i?= 0, represents there is a wall between location (x?i1, yi1) and (x?i2, y?i2), ( | x?i1?- x?i2?| + | y?i1?- y?i2?|=1, 0<= g?i?<=p )?

Following line is an integer S, represent the total number of keys in maze. (0<= S <=50).?

There are three integers in the following S lines, represents x?i1, y?i1?and q?irespectively. That means the key type of q?i?locates on location (x?i1, y?i1), (1<= qi<=p).

Output

Output the possible minimal second that Kirk could reach Spock.?

If there is no possible plan, output -1.?

Sample Input

4 4 9 9 1 2 1 3 2 1 2 2 2 0 2 1 2 2 0 2 1 3 1 0 2 3 3 3 0 2 4 3 4 1 3 2 3 3 0 3 3 4 3 0 4 3 4 4 0 2 2 1 2 4 2 1

Sample Output

14

題目大意：

? ? ?給定一個棋盤，從(1,1)走到(n,m)有的任意兩個格子之間的邊視為：通路，門，墻。通路可以直接走，門必須早到相應的鑰匙，墻永遠不能通過。鑰匙在一些給定點的格子中(同一個格子中可能有多把鑰匙)，問采取怎樣的走法可以得到最少的移動步數。

解題報告：

? ? ? ?注意這題給的坐標代表的是一個房間，而不是點，讀入的地圖代表連接這兩個房間的那條路是需要鑰匙的還是不需要鑰匙的還是墻。然后鑰匙數狀壓一下，用鄰接矩陣存圖，然后用vis三維數組存當前狀態和所得鑰匙的情況數。vis[x][y][s]表示狀態為s時到達(x,y)點是否已經到達過，s表示鑰匙的得到情況的狀態。

AC代碼：

#include<bits/stdc++.h>using namespace std; int tx[4] = {0,1,0,-1}; int ty[4] = {1,0,-1,0}; int n,m; int maze[55][55][55][55],key[55][55]; bool vis[55][55][1<<11]; struct Node {int x,y;int step;int kk;Node(int x,int y,int step,int kk):x(x),y(y),step(step),kk(kk){} };int bfs() {queue<Node> q;memset(vis,0,sizeof(vis));q.push(Node(1,1,0,key[1][1]));vis[1][1][key[1][1] ] =1;int nx,ny;while(!q.empty()) {Node cur = q.front();q.pop();if(cur.x == n && cur.y == m) return cur.step;for(int k = 0; k<4; k++) {nx = cur.x + tx[k];ny = cur.y + ty[k];int t = maze[cur.x][cur.y][nx][ny];int nowkey = cur.kk | key[nx][ny];int w = 1<<(t-1);if(nx > n || ny > m || nx <1 || ny <1) continue;if(vis[nx][ny][nowkey] == 1) continue;if(t == 0 ) continue;if(t!=-1 && (nowkey & w ) == 0) continue;vis[nx][ny][nowkey] = 1;q.push(Node(nx,ny,cur.step+1,nowkey)); }}return -1;}int main() {//n行m咧 int x1,x2,y1,y2;int g,p,k;while(~scanf("%d%d%d",&n,&m,&p) ) {scanf("%d",&k);memset(maze,-1,sizeof(maze));memset(key,0,sizeof(key));for(int i = 1; i<=k; i++) {scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&g);maze[x1][y1][x2][y2] = maze[x2][y2][x1][y1] = g;}int s;scanf("%d",&s);while(s--) {scanf("%d%d%d",&x1,&y1,&g);g--;key[x1][y1] |=(1<<g);}printf("%d\n",bfs());}return 0 ; }

總結：

? ?1.沒事不要瞎定義變量，也不要瞎定義全局變量（因為有可能定義了然后錯用了還不報錯）！這題的bfs中我剛開始就定義了x，y，然后有一個地方應該是cur.x和cur.y我用成了x，y。。。本來只是落下了cur.但誰知編譯器沒報錯！所以答案顯然是錯的。

?? 2.if中該加括號的地方一定要加括號，你咋知道在評測機上的編譯器上是怎么跑的程序。

? ?3.類似g--這樣的細節一定要注意

總結

以上是生活随笔為你收集整理的【HDU - 5094】 Maze （状态压缩+bfs）的全部內容，希望文章能夠幫你解決所遇到的問題。

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