題目999
題目信息
執(zhí)行結(jié)果
本題排行
討論區(qū)

師傅又被妖怪抓走了
時(shí)間限制：1000 ms | 內(nèi)存限制：65535 KB
難度：3

描寫敘述

話說(shuō)唐僧復(fù)得了孫行者，師徒們一心同體，共詣西方。自寶象國(guó)救了公主，承君臣送出城西。沿路饑餐渴飲，悟空便為師傅去化齋。等悟空回來(lái)，悟凈慌慌張張的對(duì)悟空說(shuō)：“不好了，不好了”，還沒(méi)等悟凈說(shuō)完，悟空說(shuō)：“師傅又被妖怪抓走了”，悟凈：“NO！” ,悟空一臉茫然。悟凈：“師傅和二師兄都被妖怪抓走了”。悟空（暈！

）。

為了防止悟空救人，妖怪先把唐憎和八戒分別藏起來(lái)，如果悟空在T分鐘之后還沒(méi)找到人。那必然是被妖怪吃掉了。如果悟空在一個(gè)n行m列的矩陣內(nèi)，悟空在每一分鐘能夠走到上，下，左，右的當(dāng)中的一個(gè)能夠走的位置，每次僅僅能走一步。

我們把發(fā)現(xiàn)定義為能夠直接看到對(duì)方，也就是說(shuō)兩個(gè)人在同一行或者同一列，而且中間沒(méi)有障礙物或者沒(méi)有其它人就能夠看到對(duì)方。

輸入
有多組測(cè)試數(shù)據(jù)，每組首先是三個(gè)正整數(shù)n , m (3<=n,m<=100), T,(0<=T<=100) 分別代表行數(shù),列數(shù)，規(guī)定的時(shí)間。接下來(lái)n 行，每行 m 個(gè)字符。

當(dāng)中’ S ’ 代表悟空的位置，’ D ’代表師傅位置，’ E ’代表八戒的位置。而且保證都僅僅有一個(gè). ’ X ’代表墻 ,’ . ’代表空地 .
輸出
每組先輸出一行Case c:(c表示當(dāng)前的組數(shù)。從1開(kāi)始計(jì)數(shù))；
接下來(lái)一行。假設(shè)悟空能夠在規(guī)定時(shí)間內(nèi)找到兩人，則輸出最少須要的時(shí)間，否則輸出-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

這道題讓我非常焦灼啊。。。開(kāi)個(gè)玩笑 哈哈

這道題的發(fā)現(xiàn)定義為能夠直接看到對(duì)方。所以是不能走X D E 僅僅能是看到

所以在錄入數(shù)據(jù)的時(shí)候 我們就提前做好預(yù)處理。

把D E的四個(gè)方向 能看到的地方都處理一下

然后就是bfs了 而在這里 我提交了幾次 發(fā)現(xiàn)都不正確 后來(lái)無(wú)意中的一個(gè)數(shù)據(jù)啟示了我

2 3 1

.S.

DXE

輸出-1

2 3 3

.S.

DXE

輸出3

聰明的你 看出來(lái)了嗎？假設(shè)我們用通常的vis數(shù)組標(biāo)記走過(guò)的路徑
，對(duì)于第二條測(cè)試數(shù)據(jù) 僅僅會(huì)輸出-1? 由于它不會(huì)走回頭路 。我又存在僥幸的心理 不用vis數(shù)組標(biāo)記了 發(fā)現(xiàn) 果然TLE

?然后就是不做了 走在路上還在想 到底在這里該怎么優(yōu)化 。。。果然 睡覺(jué)的時(shí)候被我想到了 今天早上一大早 就起來(lái)做了。

詳細(xì)方法是 假設(shè)又定義了兩個(gè)數(shù)組visE【x】【y】 visD【x】【y】分別記錄在x,y點(diǎn) 是否已經(jīng)找到過(guò)E 或D? 。

當(dāng)某個(gè)點(diǎn)已經(jīng)遍歷過(guò)

我們?cè)偻茢喈?dāng)前的visD 和visE和之前的是否一致? 假設(shè)一致 我們就不用走 假設(shè)不一致 證明我們?cè)谄渌c(diǎn)找到了D或E? 如今要回來(lái)。

詳細(xì)看代碼把

#include <stdio.h> #include <string.h> #include <queue> #include <algorithm> using namespace std; int n,m; int t; int s1,s2; int d1,d2; int e1,e2; int dir[4][2]={1,0,0,1,-1,0,0,-1}; char map[105][105]; bool visD[105][105]; bool visE[105][105]; bool vis[105][105]; struct node {int x,y;int step;bool isfindD;bool isfindE;friend bool operator<(node a,node b){return a.step>b.step;} }; void prepare(int x,int y,char ch) {char ch2;int x2,y2;if(ch=='D')ch2='E',x2=e1,y2=e2;elsech2='D',x2=d1,y2=d2;for(int i=x-1;i>=0;i--){if(map[i][y]=='X'||i==x2&&y==y2)break;if(map[i][y]=='.')map[i][y]=ch;else if(map[i][y]==ch2)map[i][y]='*';else if(map[i][y]=='S'){map[i][y]=ch;break;}}for(int i=x+1;i<n;i++){if(map[i][y]=='X'||i==x2&&y==y2)break;if(map[i][y]=='.')map[i][y]=ch;else if(map[i][y]==ch2)map[i][y]='*';else if(map[i][y]=='S'){map[i][y]=ch;break;}}for(int i=y+1;i<m;i++){if(map[x][i]=='X'||x==x2&&i==y2)break;if(map[x][i]=='.')map[x][i]=ch;else if(map[x][i]==ch2)map[x][i]='*';else if(map[x][i]=='S'){map[x][i]=ch;break;}}for(int i=y-1;i>=0;i--){if(map[x][i]=='X'||x==x2&&i==y2)break;if(map[x][i]=='.')map[x][i]=ch;else if(map[x][i]==ch2) map[x][i]='*';else if(map[x][i]=='S'){map[x][i]=ch;break;}} } bool limit(int x,int y) {if(x==d1&&y==d2)return false;if(x==e1&&y==e2)return false;if(x<0||y<0||x>=n||y>=m||map[x][y]=='X')return false;return true; } void check_result(node &temp1) {int x=temp1.x;int y=temp1.y;if(map[x][y]=='D')temp1.isfindD=true;else if(map[x][y]=='E')temp1.isfindE=true;else if(map[x][y]=='*')temp1.isfindD=temp1.isfindE=true; } int bfs(int x1,int y1,int time) {node temp1,temp2;priority_queue<node>s;while(!s.empty())s.pop();temp1.x=x1;temp1.y=y1;temp1.step=0;temp1.isfindD=temp1.isfindE=false;check_result(temp1);visE[x1][y1]=temp1.isfindE;visD[x1][y1]=temp1.isfindD;vis[x1][y1]=true;s.push(temp1);while(!s.empty()){temp1=temp2=s.top();s.pop();if(temp1.step>time)return -1;if(temp1.isfindD&&temp1.isfindE)return temp1.step; for(int i=0;i<4;i++){int x1=temp1.x+dir[i][0];int y1=temp1.y+dir[i][1];if(limit(x1,y1)&&(!vis[x1][y1]||!(visE[x1][y1]==temp1.isfindE&&visD[x1][y1]==temp1.isfindD))){temp1.x=x1;temp1.y=y1;temp1.step++;check_result(temp1);vis[x1][y1]=true;visE[x1][y1]=temp1.isfindE;visD[x1][y1]=temp1.isfindD; s.push(temp1);temp1=temp2;}}}return -1; } int main() {int ncase=1;while(~scanf("%d %d %d",&n,&m,&t)){memset(map,0,sizeof(map));for(int i=0;i<n;i++){getchar();for(int j=0;j<m;j++){scanf("%c",&map[i][j]);if(map[i][j]=='S'){s1=i;s2=j;}if(map[i][j]=='D'){d1=i;d2=j;}if(map[i][j]=='E'){e1=i;e2=j;}}}prepare(d1,d2,'D');prepare(e1,e2,'E');memset(visD,false,sizeof(visD));memset(visE,false,sizeof(visE));memset(vis,false,sizeof(vis));printf("Case %d:\n%d\n",ncase++,bfs(s1,s2,t));} }

總結(jié)

以上是生活随笔為你收集整理的nyoj999 师傅又被妖怪抓走了 (预处理+bfs+状态压缩)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。