1280: 詭異的迷宮

時間限制: 2 秒??內存限制: 128 MB
提交: 174??解決: 27
提交?狀態?

題目描述

Simple最近刷題（打游戲）刷多了，一覺醒來發現自己到了一個迷宮里，怎么也出不去了。這時傳來了一句話，告訴Simple必須按順序收集完所有的寶石，才能出迷宮。所謂的順序，就是按照每塊寶石上英文字母的順序。迷宮里面還有一些傳送門，可以傳送到任意一個另外的傳送門的位置。（你走到一個不是空地上的地方的時候，就一定會觸發相應事件，不可拒絕，從一個傳送門傳送到另一個傳送門不用再次傳送）。每走一步花費一個單位時間，傳送門到另外一個傳送門不需要時間。Simple初始就在字母為A的寶石的位置上（開局一寶石，其他全靠找）。

當Simple收集完所有寶石的時候就被傳送出迷宮。

Simple還要趕回去刷題（打游戲），你們能告訴他最少需要多長時間才能回去嗎？如果不可能出去就輸出Impossible。

輸入

多組實例，每組輸入一個n，表示迷宮的大小為n*n ?(n <= 10)
下面n行每行n個字符?
'.'表示空地，
'#'表示墻，不可以通過
'$'表示一個傳送門
大寫字母表示寶石

輸出

每個實例輸出一個數字，表示最少需要的時間，如果不能逃出迷宮，就輸出Impossible。

樣例輸入

5 A.... ####. ..B.. .#### C.DE.2 AC .B2 A# #B3 A$. ... .$B

樣例輸出

15 3 Impossible 2


/*
這題就是一個簡單的bfs，只是要注意的地方有很多。
題目要求收集寶石只能按照英文字母的順序，所以順序不對的寶石當前是當作墻來看待的，是不能走的。
收集過的寶石的地方，是可以重復走的，不然有的時候就不能收集完所有寶石，所以每收集一次寶石，就相當于重新跑一次bfs
至于傳送門，你踩到一個傳送門，必須要傳送到另一個傳送門，此時到達另外一個傳送門就不能觸發效果了
*/

（我debug一個下午。。。）
附本人debug一下午的代碼： 1 #include <cstdio> 2 #include <cmath> 3 #include <iostream> 4 #include <vector> 5 #include <set> 6 #include <sstream> 7 #include <algorithm> 8 #include <string> 9 #include <cstring> 10 using namespace std; 11 const int maxn = 15; 12 string st[maxn]; 13 struct nod{ 14 int x; 15 int y; 16 }tran[1050],nu[1050]; 17 int vis[maxn][maxn]; 18 int dir[5][2] = {{0,1},{1,0},{0,-1},{-1,0}}; 19 int n; 20 int f = 0; 21 int sx,sy,len; 22 int cnt = 0,all = 0; //寶石 23 int head = 0,tail = 0; 24 void bfs(int sx,int sy) { 25 int xx,yy; 26 head = 0,tail = 1; 27 nu[head].x = sx; 28 nu[head].y = sy; 29 while(head != tail) { 30 31 int i; 32 for( i = 0; i < 4; i++) { 33 xx = nu[head].x + dir[i][0]; 34 yy = nu[head].y + dir[i][1]; 35 if(xx >= 0 && xx < n && yy >= 0 && yy < n && st[xx][yy] != '#' && !vis[xx][yy] ) { 36 if(st[xx][yy] == '.') { 37 nu[tail].x = xx; 38 nu[tail++].y = yy; 39 vis[xx][yy] = vis[nu[head].x][nu[head].y] + 1; 40 41 // cout<<vis[xx][yy]<<endl; 42 } 43 if(st[xx][yy] == '$') { 44 45 vis[xx][yy] = vis[nu[head].x][nu[head].y] + 1; 46 for(int j = 0; j < len; j++) { 47 if(!vis[tran[j].x][tran[j].y]) { 48 49 50 nu[tail].x = tran[j].x; 51 nu[tail++].y = tran[j].y; 52 vis[tran[j].x][tran[j].y] = vis[xx][yy]; 53 // cout<< vis[tran[j].x][tran[j].y]<<endl; 54 continue; 55 } 56 } 57 } 58 else { 59 if(st[xx][yy] - 'A' == cnt + 1) { 60 // cout<<st[nu[head].x][nu[head].y]<<endl; 61 int u = vis[nu[head].x][nu[head].y] + 1; 62 nu[tail].x = xx; 63 nu[tail++].y = yy; 64 st[xx][yy] = '.'; 65 head = tail - 1; 66 // cout<<xx<<yy<<"!!!"<<endl; 67 cnt++; 68 f = 1; 69 70 71 // cout<<"u "<<u<<endl; 72 memset(vis,0,sizeof(vis)); 73 vis[nu[head].x][nu[head].y] = u; 74 // cout<<vis[nu[head].x][nu[head].y]<<"!!"<<endl; 75 // if(vis[nu[head].x][nu[head].y] == 5) 76 77 break; 78 // cout<<nu[head].x<<" "<<nu[head].y<<endl; 79 } 80 81 } 82 } 83 } 84 // cout<<i<<endl; 85 if(cnt == all) break; 86 87 88 if(f == 1) { 89 f = 0; 90 continue; 91 } 92 head++; 93 } 94 } 95 int main() { 96 ios::sync_with_stdio(false); 97 98 while(cin>>n) { 99 memset(vis,0,sizeof(vis)); 100 cnt = 0,all = 0; //寶石 101 head = 0,tail = 0; 102 sx = 0,sy = 0,len = 0; 103 f = 0; 104 for(int i = 0; i < n; i++) { 105 cin>>st[i]; 106 } 107 108 109 for(int i = 0; i < n; i++) { 110 for(int j = 0; j < n; j++) { 111 112 if(st[i][j] == 'A') { 113 st[i][j] = '.'; 114 sx = i; 115 sy = j; 116 vis[i][j] = 1; 117 } 118 if(st[i][j] > 'A' && st[i][j] <= 'Z') all++; 119 120 if(st[i][j] == '$') { 121 tran[len].x = i; 122 tran[len++].y = j; 123 } 124 } 125 126 } 127 // cout<<all<<endl; 128 bfs(sx,sy); 129 130 if(cnt != all) cout<<"Impossible"<<endl; 131 else cout<<vis[nu[head].x][nu[head].y]-1<<endl; 132 } 133 return 0; 134 } View Code

?? 附標程：

1 #include<queue> 2 #include<cstdio> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 7 using namespace std; 8 9 struct door 10 { 11 int x,y; 12 }e[110]; 13 14 int n,cnt,ce; 15 char a[15][15]; 16 int b[15][15]; 17 int dir[4][2] = {0,1,0,-1,1,0,-1,0}; 18 19 20 struct node 21 { 22 int x,y,s,cnt; 23 }; 24 25 void bfs(int x,int y) 26 { 27 memset(b,0,sizeof(b)); 28 a[x][y] = '.'; 29 b[x][y] = 1; 30 queue<node> q; 31 node t,next; 32 t.x = x; 33 t.y = y; 34 t.s = 0; 35 t.cnt = 1; 36 q.push(t); 37 while(!q.empty()) 38 { 39 t = q.front(); 40 q.pop(); 41 if(t.cnt == cnt) 42 { 43 printf("%d\n",t.s); 44 return; 45 } 46 for(int i=0;i<4;i++) 47 { 48 int tx = t.x + dir[i][0]; 49 int ty = t.y + dir[i][1]; 50 if(tx < 0 || ty < 0 || tx >= n || ty >= n) 51 continue; 52 if(a[tx][ty] == '#' || b[tx][ty]) 53 continue; 54 if(a[tx][ty] >= 'A' && a[tx][ty] <= 'Z' && a[tx][ty] != 'A' + t.cnt) 55 continue; 56 if(a[tx][ty] >= 'A' && a[tx][ty] <= 'Z') 57 { 58 next.x = tx; 59 next.y = ty; 60 next.s = t.s + 1; 61 next.cnt = t.cnt + 1; 62 a[tx][ty] = '.'; 63 memset(b,0,sizeof(b)); 64 while(!q.empty()) 65 q.pop(); 66 b[tx][ty] = 1; 67 q.push(next); 68 break; 69 } 70 if(a[tx][ty] == '$') 71 { 72 for(int j=0;j<ce;j++) 73 { 74 if(e[j].x == tx && e[j].y == ty) 75 continue; 76 if(b[e[j].x][e[j].y]) 77 continue; 78 next.x = e[j].x; 79 next.y = e[j].y; 80 next.s = t.s + 1; 81 next.cnt = t.cnt; 82 b[e[j].x][e[j].y] = 1; 83 q.push(next); 84 continue; 85 } 86 continue; 87 } 88 next.x = tx; 89 next.y = ty; 90 next.s = t.s + 1; 91 next.cnt = t.cnt; 92 b[tx][ty] = 1; 93 q.push(next); 94 } 95 } 96 printf("Impossible\n"); 97 } 98 int main(void) 99 { 100 int T,i,j,x,y; 101 while(scanf("%d",&n)==1) 102 { 103 cnt = 0; 104 ce = 0; 105 for(i=0;i<n;i++) 106 { 107 scanf("%s",a[i]); 108 for(j=0;j<n;j++) 109 { 110 if(a[i][j] == 'A') 111 x = i, y = j; 112 if(a[i][j] >= 'A' && a[i][j] <= 'Z') 113 cnt++; 114 if(a[i][j] == '$') 115 { 116 e[ce].x = i; 117 e[ce++].y = j; 118 } 119 } 120 } 121 bfs(x,y); 122 } 123 124 return 0; 125 } View Code

?

轉載于:https://www.cnblogs.com/zmin/p/7599489.html

總結

以上是生活随笔為你收集整理的haut-1280 诡异的迷宫的全部內容，希望文章能夠幫你解決所遇到的問題。

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