生活随笔
收集整理的這篇文章主要介紹了
nyoj 82
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
迷宮尋寶（一）
時間限制：
1000?ms ?|? 內存限制：
65535?KB 難度：
4
描述
一個叫ACM的尋寶者找到了一個藏寶圖，它根據藏寶圖找到了一個迷宮，這是一個很特別的迷宮，迷宮里有N個編過號的門（N<=5)，它們分別被編號為A,B,C,D,E.為了找到寶藏，ACM必須打開門，但是，開門之前必須在迷宮里找到這個打開這個門所需的所有鑰匙（每個門都至少有一把鑰匙），例如：現在A門有三把鑰匙，ACM就必須找全三把鑰匙才能打開A門。現在請你編寫一個程序來告訴ACM，他能不能順利的得到寶藏。
?
輸入輸入可能會有多組測試數據（不超過10組）。
每組測試數據的第一行包含了兩個整數M,N(1<N,M<20)，分別代表了迷宮的行和列。接下來的M每行有N個字符，描述了迷宮的布局。其中每個字符的含義如下：
.表示可以走的路
S:表示ACM的出發點
G表示寶藏的位置
X表示這里有墻，ACM無法進入或者穿過。
A,B,C,D,E表示這里是門，a,b,c,d,e表示對應大寫字母的門上的鑰匙。
注意ACM只能在迷宮里向上下左右四個方向移動。
最后，輸入0 0表示輸入結束。輸出每行輸出一個YES表示ACM能找到寶藏，輸出NO表示ACM找不到寶藏。樣例輸入 4 4
S.X.
a.X.
..XG
....
3 4
S.Xa
.aXB
b.AG
0 0 樣例輸出 YES
NO
解題思路：這道題目唯一要注意的就是門的鑰匙必須都要拿到才能打開，所以弄一個數組記錄下鑰匙的個數，每次遇到一個鑰匙就減一次，并且把這一點置為'.'，由于可能某一點會出現多次，而鑰匙的種類也小于5，所以可以狀態壓縮，每一種鑰匙代表一個位，防止重復。。。
我測的很多數據都過了，就是一直WA......
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;int n,m,sx,sy,ex,ey;
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int num[5];
char map[20][20];
bool vis[20][20][50],door[5];
struct node
{int x,y;int status;
};bool bfs()
{queue<node> q;node cur,next;int x,y,status;cur.x = sx; cur.y = sy; cur.status = 0;q.push(cur);while(!q.empty()){cur = q.front();q.pop();for(int i = 0; i < 4; i++){x = cur.x + dir[i][0];y = cur.y + dir[i][1];status = cur.status;if(x == ex && y == ey) return true;if(x < 0 || x >= m || y < 0 || y >= n || map[x][y] == 'X') continue;if(map[x][y] == '.'){if(vis[x][y][status] == true) continue;next.x = x; next.y = y; next.status = status;vis[x][y][status] = true;q.push(next);}else{if(map[x][y] >= 'A' && map[x][y] <= 'Z'){if(num[map[x][y] - 'A'] == 0 && door[map[x][y] - 'A'] == true) //所有的鑰匙都找到{next.x = x; next.y = y; next.status = status;q.push(next);vis[x][y][status] = true;map[x][y] = '.';}}else //該位置是鑰匙{num[map[x][y] - 'a']--;next.x = x; next.y = y;if(num[map[x][y] - 'a'] == 0) //鑰匙都找到了{status = status | (1<<(map[x][y] - 'a'));}next.status = status;q.push(next);vis[x][y][status] = true;map[x][y] = '.';}}}}return false;
}int main()
{while(cin>>m>>n && m + n){for(int i = 0; i < m; i++){getchar();scanf("%s",map[i]);}memset(vis,false,sizeof(vis));memset(door,false,sizeof(door));memset(num,0,sizeof(num));for(int i = 0; i < m; i++)for(int j = 0; j < n; j++){if(map[i][j] == 'S')sx = i, sy = j;else if(map[i][j] == 'G')ex = i, ey = j;else if(map[i][j] >= 'a' && map[i][j] <= 'z'){num[map[i][j] - 'a']++;door[map[i][j] - 'a'] = true;}}if(bfs()) cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0;
}
總結
以上是生活随笔為你收集整理的nyoj 82的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
