http://acm.nyist.net/JudgeOnline/problem.php?pid=999? ? ??

題解： ??把師傅所在行和列標記為 1 狀態 ? 'd'

二師兄所在行和列標記為 2 狀態 ? 'e'

如果師傅和二師兄在同一行或同一列，重合的部分標記為3狀態 'x'

要想把師傅和二師兄都找到：

要么先找到師傅，再找到二師兄；

? ? ?要么先找到二師兄，再找到師傅；

? ? ?要么同時找到

#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");} }

總結

以上是生活随笔為你收集整理的nyoj-999 师傅又被妖怪抓走了的全部內容，希望文章能夠幫你解決所遇到的問題。

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