链接:hdu4528
题解
- bfs好题,简单但是有点烦,注意E,D要当成墙2333.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
using namespace std;
const int N=1e2+7;
typedef pair<int,int> s;
struct node{
int x,y,dis,cnt;
inline void init(int a,int b,int c,int d){x=a;y=b;dis=c;cnt=d;}
}a;
s A,B,S;
queue<node> q;
char str[N];
int map[N][N],vis[4][N][N],n,m,t,T;
int dx[]={0,-1,1,0,0};
int dy[]={0,0,0,-1,1};
inline int judge(int x,int y){return x<1||x>n||y<1||y>m||map[x][y]==4;}
inline void init(){
memset(vis,0,sizeof vis);
while(!q.empty())q.pop();
rep(i,1,n){
scanf("%s",str+1);
rep(j,1,m){
map[i][j]=(str[j]!='.'&&str[j]!='S')?4:0;
if(str[j]=='S')S=s(i,j);
else if(str[j]=='E')A=s(i,j);
else if(str[j]=='D')B=s(i,j);
}
}
rep(k,1,2){
int x,y;
if(k==1)x=A.first,y=A.second;
else x=B.first,y=B.second;
rep(j,1,4)rep(l,1,j<3?n:m){
int nx=x+dx[j]*l,ny=y+dy[j]*l;
if(judge(nx,ny))break;
map[nx][ny]+=k;
}
}
}
int main(){
scanf("%d",&T);
rep(cse,1,T){
scanf("%d%d%d",&n,&m,&t);
init();
int res=0,ans=-1;
a.init(S.first,S.second,0,map[S.first][S.second]);
if(a.cnt==4)a.cnt=0;
q.push(a);vis[a.cnt][S.first][S.second];
while(!q.empty()){
int x=q.front().x,y=q.front().y,dis=q.front().dis,cnt=q.front().cnt;
q.pop();
if(cnt==3){ans=dis;break;}
rep(i,1,4){
int nx=x+dx[i],ny=y+dy[i];
if(judge(nx,ny)||dis+1>t)continue;
int ncnt=cnt+((map[nx][ny]!=cnt)?map[nx][ny]:0);
if(ncnt>3)ncnt=3;
if(vis[ncnt][nx][ny])continue;
a.init(nx,ny,dis+1,ncnt);
vis[ncnt][nx][ny]=1;
q.push(a);
}
}
printf("Case %d:\n%d\n",cse,ans);
}
return 0;
}