师傅又被妖怪抓走了
描述 有多組測試數據，每組首先是三個正整數n , m (3<=n,m<=100), T,(0<=T<=100) 分別代表行數,列數，規定的時間。接下來n 行，每行 m 個字符。其中’ S ’ 代表悟空的位置，’ D ’代表師傅位置，’ E ’代表八戒的位置。并且保證都只有一個. ’ X ’代表墻 ,’ . ’代表空地 . 輸出每組先輸出一行Case c:(c表示當前的組數，從1開始計數)；
接下來一行，如果悟空可以在規定時間內找到兩人，則輸出最少需要的時間，否則輸出-1。 樣例輸入 5 6 3
XXD...
....E.
....X.
....S.
......
5 6 3
XDX...
....E.
......
....S.
......
5 6 8
XXDX..
.XEX..
......
....S.
...... 樣例輸出 Case 1:
-1
Case 2:
3
Case 3:
-1
話說唐僧復得了孫行者，師徒們一心同體，共詣西方。自寶象國救了公主，承君臣送出城西，沿路饑餐渴飲，悟空便為師傅去化齋，等悟空回來，悟凈慌慌張張的對悟空說：“不好了，不好了”，還沒等悟凈說完，悟空說：“師傅又被妖怪抓走了”，悟凈：“NO！”?,悟空一臉茫然，悟凈：“師傅和二師兄都被妖怪抓走了”。悟空（暈！）。為了防止悟空救人，妖怪先把唐憎和八戒分別藏起來，如果悟空在T分鐘之后還沒找到人，那必定是被妖怪吃掉了。假設悟空在一個n行m列的矩陣內，悟空在每一分鐘可以走到上，下，左，右的其中的一個可以走的位置，每次只能走一步。我們把發現定義為可以直接看到對方，也就是說兩個人在同一行或者同一列，并且中間沒有障礙物或者沒有其他人就可以看到對方。
輸入接下來一行，如果悟空可以在規定時間內找到兩人，則輸出最少需要的時間，否則輸出-1。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<cmath> using namespace std; const int dx[] = {1,-1,0,0}; const int dy[] = {0,0,1,-1}; bool vis[105][105][5]; char map[105][105]; int n,m,t; struct node{int x,y;int step,st; }; bool ok(int x,int y){//判斷的是否能走，可以把師傅或二師兄看做墻即不能走if(map[x][y] == 'E'|| map[x][y] == 'D' || map[x][y] == 'X')return false;return true; } char graph(char c,int Bool){//師傅或二師兄所在的行和列標記有多不同if((Bool && c == 'e') || (!Bool && c == 'd'))return 'x';//'x'可以記為把師傅和二師兄都被找到的狀態return Bool?'d':'e'; } void solve(int x,int y,int Bool)//處理師傅或二師兄所在的行和列 {for(int i = x + 1;i < n && ok(i,y);i++)map[i][y] = graph(map[i][y],Bool);for(int i = x - 1;i >= 0 && ok(i,y);i--)map[i][y] = graph(map[i][y],Bool);for(int i = y + 1;i < m && ok(x,i);i++)map[x][i] = graph(map[x][i],Bool);for(int i = y - 1;i >= 0 && ok(x,i);i--)map[x][i] = graph(map[x][i],Bool); } int getST(char c,int st){//處理當前所走的狀態if(c == 'd') st |= 1;else if(c == 'e') st |= 2;else if(c == 'x') st |= 3;return st; } bool find(int x,int y,int st){if(!ok(x,y)) return false;if(vis[x][y][st]) return false;if(x < 0 || x > n || y < 0 || y > m) return false;return true; } int bfs(int sta,int end){memset(vis,false,sizeof(vis));node p,q;queue<node> Q;p.x = sta,p.y = end,p.step = 0;p.st = getST(map[sta][end],0);vis[p.x][p.y][p.st] = true;Q.push(p);while(!Q.empty()){q = Q.front();Q.pop();if(q.st == 3) return q.step;//問是否能達到3的狀態，即師傅和二師兄都被找到for(int i = 0;i < 4;i++){p.x = dx[i] + q.x;p.y = dy[i] + q.y;p.st = q.st;if(find(p.x,p.y,p.st)){p.st = getST(map[p.x][p.y],p.st);p.step = q.step + 1;vis[p.x][p.y][p.st] = true;Q.push(p);}}}return 900; } int main(){int sx,sy,ca = 1;while(~scanf("%d%d%d",&n,&m,&t)){getchar();for(int i = 0;i < n;i++){cin >> map[i];for(int j = 0;j < m;j++)if(map[i][j] == 'S')sx = i,sy = j;}for(int i = 0;i < n;i++){for(int j = 0;j < m;j++){if(map[i][j] == 'D')solve(i,j,1);else if(map[i][j] == 'E')solve(i,j,0);}}printf("Case %d:\n",ca++);int ans = bfs(sx,sy);if(ans <= t)printf("%d\n",ans);else puts("-1");} }
總結
- 上一篇： 图像有用区域 bfs
- 下一篇： Failed to install Dr