一、题意
小明S在迷宫n*m中找大明D和二明E，障碍物X不能走，问你计算是否能在时间t内找到大明和二明
二、分析
2.1与普通的BFS不同，这里可以走回头路，这里应该建立四维的标记数组标记数组，例如vis[1][0][nx][ny]表示已经找到D且没找到E且位置为（nx,ny）的状态，相同状态不可重复进入队列
2.2根据样例二可知D，E的位置不可走，起始点S的位置等价于'.'
2.3为了提高效率可预处理一下标记所有可以‘看到’D和E的点
三、代码
# include <iostream>
# include <cstdio>
# include <queue>
# include <cstring>
using namespace std;
const int maxn=;
int cnt,T,n,m,t,vis[][][maxn][maxn];
int seeE[maxn][maxn],seeD[maxn][maxn];
char map[maxn][maxn];
int Dx,Dy,Ex,Ey,Sx,Sy;
int dx[]={-,,,};
int dy[]={,,,-};
struct Node
{
int tim,x,y,e,d;
Node(){}
Node(int ee,int dd,int tt,int xx,int yy)
{
e=ee;
d=dd;
tim=tt;
x=xx;
y=yy;
}
};
void Init()
{
scanf("%d%d%d",&n,&m,&t);
for(int i=;i<n;i++)
scanf("%s",map[i]);
//for(int i=0;i<n;i++)
// printf("%s\n",map[i]);
memset(vis,,sizeof(vis));
memset(seeD,,sizeof(seeD));
memset(seeE,,sizeof(seeE));
for(int i=;i<n;i++)
for(int j=;j<m;j++)
{
if(map[i][j]=='S')
{
Sx=i;
Sy=j;
}
if(map[i][j]=='D')
{
Dx=i;
Dy=j;
for(int i=Dx+;i<n;i++)
if(map[i][Dy]=='.'||map[i][Dy]=='S')
seeD[i][Dy]=;
else break;
for(int i=Dx-;i>=;i--)
if(map[i][Dy]=='.'||map[i][Dy]=='S')
seeD[i][Dy]=;
else break;
for(int j=Dy+;j<m;j++)
if(map[Dx][j]=='.'||map[Dx][j]=='S')
seeD[Dx][j]=;
else break;
for(int j=Dy-;j>=;j--)
if(map[Dx][j]=='.'||map[Dx][j]=='S')
seeD[Dx][j]=;
else break;
}
if(map[i][j]=='E')
{
Ex=i;
Ey=j;
for(int i=Ex+;i<n;i++)
if(map[i][Ey]=='.'||map[i][Ey]=='S')
seeE[i][Ey]=;
else break;
for(int i=Ex-;i>=;i--)
if(map[i][Ey]=='.'||map[i][Ey]=='S')
seeE[i][Ey]=;
else break;
for(int j=Ey+;j<m;j++)
if(map[Ex][j]=='.'||map[Ex][j]=='S')
seeE[Ex][j]=;
else break;
for(int j=Ey-;j>=;j--)
if(map[Ex][j]=='.'||map[Ex][j]=='S')
seeE[Ex][j]=;
else break;
}
}
}
int Solve()
{
int res=-;
queue<Node> Q;
map[Sx][Sy]='.';
Q.push(Node(seeE[Sx][Sy],seeD[Sx][Sy],,Sx,Sy));
vis[seeE[Sx][Sy]][seeD[Sx][Sy]][Sx][Sy]=;
while(!Q.empty())
{
Node temp=Q.front();
Q.pop();
//printf("%d %d %d %d %d\n",temp.e,temp.d,temp.x,temp.y,temp.tim);
if(temp.tim>t) break;
if(temp.e+temp.d==)
{
res=temp.tim;
break;
}
for(int i=;i<;i++)
{
int nx=temp.x+dx[i];
int ny=temp.y+dy[i];
//printf("%d %d\n",nx,ny);
if(nx>=&&ny>=&&nx<n&&ny<m&&map[nx][ny]=='.')
{
int ne=seeE[nx][ny]?:temp.e;
int nd=seeD[nx][ny]?:temp.d;
//if(nx==3&&ny==3) {printf("test:%d\n",vis[ne][nd][nx][ny]); break;}
if(!vis[ne][nd][nx][ny])
{
vis[ne][nd][nx][ny]=;
Q.push(Node(ne,nd,temp.tim+,nx,ny));
}
}
}
}
return res;
}
int main()
{
scanf("%d",&T);
for(int i=;i<=T;i++)
{
Init();
int ans=Solve();
printf("Case %d:\n%d\n",i,ans);
}
return ;
}