hdu 2216 bfs

题目大意：两个东西朝相同方向移动
Sample Input
4 4
XXXX
.Z..
.XS.
XXXX
4 4
XXXX
.Z..
.X.S
XXXX
4 4
XXXX
.ZX.
.XS.
XXXX
Sample Output
1
1
Bad Luck!

由于两个棋子必然有一个移动。所以假设其中一个一直移动即可，比较水了

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<queue>
 7 using namespace std;
 8 int n,m,t;
 9 int d1[4][2]={1,0,0,1,-1,0,0,-1};
10 int d2[4][2]={-1,0,0,-1,1,0,0,1};
11 char s[25][25];
12 int vis[25][25][25][25];
13 struct node
14 {
15     int x1,y1,s,x2,y2;
16     node(){}
17     node(int xx,int yy,int xxx,int yyy,int ss)
18     {
19         x1=xx;y1=yy;x2=xxx;y2=yyy;s=ss;
20     }
21 }st,ed;
22 void bfs()
23 {
24     queue<node> q;
25     node now,next;
26     while(!q.empty())   q.pop();
27     q.push(node(st.x1,st.y1,st.x2,st.y2,0));
28     while(!q.empty())
29     {
30         now=q.front();
31         q.pop();
32         //printf("%d %d %d %d %d
",now.x1,now.y1,now.x2,now.y2,now.s);
33         if(fabs(now.x1-now.x2)+fabs(now.y1-now.y2)<2)
34         {
35             printf("%d
",now.s);
36             return;
37         }
38         for(int i=0;i<4;i++)            //肯定有一个棋子是移动的，以这个棋子作为判断依据
39         {
40             next.x1=now.x1+d1[i][0];
41             next.y1=now.y1+d1[i][1];
42             next.x2=now.x2+d2[i][0];
43             next.y2=now.y2+d2[i][1];
44             if(next.x1<0||next.x1>=n||next.y1<0||next.y1>=m||s[next.x1][next.y1]=='X') continue;       //这棋子必须移动
45             if(next.x2<0||next.x2>=n||next.y2<0||next.y2>=m||s[next.x2][next.y2]=='X')
46             {
47                 next.x2=now.x2,next.y2=now.y2;
48             }
49             if(vis[next.x1][next.y1][next.x2][next.y2]) continue;
50             vis[next.x1][next.y1][next.x2][next.y2]=1;
51             next.s=now.s+1;
52             q.push(next);
53         }
54     }
55     printf("Bad Luck!
");
56 }
57 int main()
58 {
59     int i,j,k;
60     freopen("1.in","r",stdin);
61     while(scanf("%d%d",&n,&m)!=EOF)
62     {
63         for(i=0;i<n;i++)
64         {
65             scanf("%s",s[i]);
66             for(j=0;j<m;j++)
67             {
68                 if(s[i][j]=='Z')    st.x1=i,st.y1=j;
69                 if(s[i][j]=='S')    st.x2=i,st.y2=j;
70             }
71         }
72         memset(vis,0,sizeof(vis));
73         bfs();
74     }
75     return 0;
76 }