nyoj 999： 点击打开题目链接
题目思路，处理一下地图，把 D E 能看到的地方标记一下。然后就是暴力广搜一下。标记状态，因为同样在同一个点，但是你刚出发到达那点和找到D之后到达相同的点和找到E之后到达相同的点，这3中状态是不同的。用vis[x][y][3]
来标记状态，标记状态知道这题就AC了。
还有另外的思路就是把它们一个一个搜，S–>D–>E S–>D–>E S–>D,E; 分别广搜，取min即可。
下面是第一种，标记状态的方法。另外一种就不写了。
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string>
#include<string.h>
#include<queue>using namespace std;
typedef long long int LL;
typedef short int sint;
const int INF=~(1<<31);
const int MM=105;int n,m,times;
sint dir[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};
char maps[MM][MM];
bool vis[MM][MM][3];
struct node
{
short int x,y,step,now;
};
bool is_out(sint x,sint y)
{
if(x>=0&&x<n&&y>=0&&y<m) return true;
return false;
}
int bfs(int sx,int sy)
{
node first,second;
if(maps[sx][sy]=='e') first.now=2;
else if(maps[sx][sy]=='d') first.now=1;
else if(maps[sx][sy]=='f') first.now=3;
else first.now=0;
queue<node>q;
first.step=0,first.x=(sint)sx,first.y=(sint)sy;
q.push(first);
while(!q.empty())
{
first=q.front();
q.pop();
// printf("step=%d x=%d y=%d now=%d\n",(int)first.step,first.x,first.y,first.now);
if(first.now==3) return first.step;
if(first.step>times) return -1;
for(int i=0; i<4; i++)
{
sint x=first.x+dir[i][0],y=first.y+dir[i][1];
if(is_out(x,y)&&vis[x][y][first.now]==0&&maps[x][y]!='X')
{
int now=first.now;
second.now=now;
vis[x][y][first.now]=true;
if(maps[x][y]=='f') second.now=3;
if(maps[x][y]=='d'&&now==2) second.now=3;
else if(maps[x][y]=='d') second.now=1;
if(maps[x][y]=='e'&&now==1) second.now=3;
else if(maps[x][y]=='e') second.now=2;
if(second.now!=3) vis[x][y][second.now]=true;
second.step=first.step+1,second.x=x,second.y=y;
q.push(second);
}
}
}
return -1;
}
void set_map(int dx,int dy,int ex,int ey)
{
int x,y;
for(x=dx+1,y=dy; is_out(x,y)&&maps[x][y]=='.'; x++) maps[x][y]='d';
for(x=dx-1,y=dy; is_out(x,y)&&maps[x][y]=='.'; x--) maps[x][y]='d';
for(x=dx,y=dy+1; is_out(x,y)&&maps[x][y]=='.'; y++) maps[x][y]='d';
for(x=dx,y=dy-1; is_out(x,y)&&maps[x][y]=='.'; y--) maps[x][y]='d'; for(x=ex+1,y=ey; is_out(x,y)&&(maps[x][y]=='.'||maps[x][y]=='d'); x++)
if(maps[x][y]=='d') maps[x][y]='f';
else maps[x][y]='e';
for(x=ex-1,y=ey; is_out(x,y)&&(maps[x][y]=='.'||maps[x][y]=='d'); x--)
if(maps[x][y]=='d') maps[x][y]='f';
else maps[x][y]='e';
for(x=ex,y=ey+1; is_out(x,y)&&(maps[x][y]=='.'||maps[x][y]=='d'); y++)
if(maps[x][y]=='d') maps[x][y]='f';
else maps[x][y]='e';
for(x=ex,y=ey-1; is_out(x,y)&&(maps[x][y]=='.'||maps[x][y]=='d'); y--)
if(maps[x][y]=='d') maps[x][y]='f';
else maps[x][y]='e';
}
void p_m()
{
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
printf("%c",maps[i][j]);
printf("\n");
}
}
int main(void)
{
int cases=0;
while(cin>>n>>m>>times)
{
int i,j,sx,sy,dx,dy,ex,ey;
memset(maps,0,sizeof(maps));
memset(vis,0,sizeof(vis));
for(i=0; i<n; i++)
{
cin>>maps[i];
for(j=0; j<m; j++)
{
if(maps[i][j]=='S') maps[i][j]='.',sx=i,sy=j;
if(maps[i][j]=='D') dx=i,dy=j;
if(maps[i][j]=='E') ex=i,ey=j;
}
}
set_map(dx,dy,ex,ey);
maps[dx][dy]='X';
maps[ex][ey]='X';
printf("Case %d:\n%d\n",++cases,bfs(sx,sy));
}
return 0;
}
