师傅又被妖怪抓走了
时间限制：1000 ms | 内存限制：65535 KB
难度：3
- 描述
话说唐僧复得了孙行者，师徒们一心同体，共诣西方。自宝象国救了公主，承君臣送出城西，沿路饥餐渴饮，悟空便为师傅去化斋，等悟空回来，悟净慌慌张张的对悟空说：“不好了，不好了”，还没等悟净说完，悟空说：“师傅又被妖怪抓走了”，悟净：“NO！” ,悟空一脸茫然，悟净：“师傅和二师兄都被妖怪抓走了”。悟空（晕！）。为了防止悟空救人，妖怪先把唐憎和八戒分别藏起来，如果悟空在T分钟之后还没找到人，那必定是被妖怪吃掉了。假设悟空在一个n行m列的矩阵内，悟空在每一分钟可以走到上，下，左，右的其中的一个可以走的位置，每次只能走一步。我们把发现定义为可以直接看到对方，也就是说两个人在同一行或者同一列，并且中间没有障碍物或者没有其他人就可以看到对方。
- 输入
- 有多组测试数据，每组首先是三个正整数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 解题思路：首先将图处理一下，处理成可以表示在某点可以找到某人或两人。然后在搜到某人后搜另外一个或者同时搜到两人。如果搜到其中一人，然后再搜另外一人。这就是双广搜，先搜一个中间结果，再在这个基础上搜另外未完成的结果。但是需注意，不是先搜到的就是最优结果。所以需要把能成功搜到两人的路径都搜一遍。取最小值。#include<bits/stdc++.h>
using namespace std;
char Map[105][105];
int mark[105][105];
int vis[105][105];
int f[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int n,m,ans,t;
const int INF=1e9;
struct Monkey{
int x,y;
int step;
};
bool CanTravle(int ti,int tj){ //判断是否可以走
if(Map[ti][tj]=='X'||Map[ti][tj]=='D'||Map[ti][tj]=='E'){
return 0;
}else{
return 1;
}
}
char trans(int i,int j,int cas){ //转化字符
if(cas&&Map[i][j]=='e'||(!cas&&Map[i][j]=='d')){
return 'o';
}
return cas ? 'd': 'e';
}
void Change(int si,int sj,int cas){ //把D、E所在的行列能走的变为d和e，把交叉点变为o
int i,j;
for(i=si+1;i<=n&&CanTravle(i,sj);i++)
Map[i][sj]=trans(i,sj,cas);
for(i=si-1;i>=1&&CanTravle(i,sj);i--)
Map[i][sj]=trans(i,sj,cas);
for(j=sj+1;j<=m&&CanTravle(si,j);j++)
Map[si][j]=trans(si,j,cas);
for(j=sj-1;j>=1&&CanTravle(si,j);j--)
Map[si][j]=trans(si,j,cas);
}
queue<Monkey>Q;
queue<Monkey>Qde;
int BFSde(int cas){ //在找到八戒或师父后找另外一个
Monkey st,tmp;
while(!Qde.empty()){
st=Qde.front();
Qde.pop();
if(st.step>t)
continue;
if(cas&&Map[st.x][st.y]=='e'||(!cas&&Map[st.x][st.y]=='d')||Map[st.x][st.y]=='o'){
return st.step;
}
int i,j,tx,ty,tsp;
for(i=0;i<4;i++){
tx=st.x+f[i][0];
ty=st.y+f[i][1];
if(tx<=n&&tx>=1&&ty<=m&&ty>=1&&(!vis[tx][ty])&&CanTravle(tx,ty)){
tsp=st.step+1;
vis[tx][ty]=1;
tmp.x=tx,tmp.y=ty,tmp.step=tsp;
Qde.push(tmp);
}
}
}
return INF;
}
void BFS(){ //找到八戒或师父或同时找到两人
Monkey st,tmp;
ans=INF;
while(!Q.empty()){
st=Q.front();
Q.pop();
if(st.step>t)
continue;
if(Map[st.x][st.y]=='o'){
ans=min(ans,st.step);
}else if(Map[st.x][st.y]=='e'){
while(!Qde.empty())
Qde.pop();
Qde.push(st);
memset(vis,0,sizeof(vis));
vis[st.x][st.y]=1;
ans=min(ans,BFSde(0));
}else if(Map[st.x][st.y]=='d'){
while(!Qde.empty())
Qde.pop();
Qde.push(st);
memset(vis,0,sizeof(vis));
vis[st.x][st.y]=1;
ans=min(ans,BFSde(1));
}
int tx,ty,tsp,i,j;
for(i=0;i<4;i++){
tx=st.x+f[i][0];
ty=st.y+f[i][1];
if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&CanTravle(tx,ty)&&(!mark[tx][ty])){
mark[tx][ty]=1;
tsp=st.step+1;
tmp.x=tx,tmp.y=ty,tmp.step=tsp;
Q.push(tmp);
}
}
}
}
int main(){
int i,j,k,cnt=0;
Monkey st;
while(scanf("%d%d%d",&n,&m,&t)!=EOF){
memset(mark,0,sizeof(mark));
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
cin>>Map[i][j];
if(Map[i][j]=='S'){
st.x=i;
st.y=j;
st.step=0;
}
}
}
for(i=1;i<=n;i++){ //处理图
for(j=1;j<=m;j++){
if(Map[i][j]=='D'){
Change(i,j,1);
}else if(Map[i][j]=='E'){
Change(i,j,0);
}
}
}
while(!Q.empty())
Q.pop();
Q.push(st);
mark[st.x][st.y]=1;
BFS();
if(ans>t){
printf("Case %d:\n-1\n",++cnt);
}else{
printf("Case %d:\n%d\n",++cnt,ans);
}
}
return 0;
} /* 5 6 30
XDX...
....E.
...S..
......
...... 7 6 5
......
.D.X..
X.X...
X.....
X.X...
.E....
...S..
*/