poj3083(Children of the Candy Corn)

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <sstream>
  4 #include <cstdlib>
  5 #include <cstring>
  6 #include <cstdio>
  7 #include <string>
  8 #include <bitset>
  9 #include <vector>
 10 #include <queue>
 11 #include <stack>
 12 #include <cmath>
 13 #include <list>
 14 //#include <map>
 15 #include <set>
 16 using namespace std;
 17 /***************************************/
 18 #define ll long long
 19 #define int64 __int64
 20 /***************************************/
 21 const int INF = 0x7f7f7f7f;
 22 const double eps = 1e-8;
 23 const double PIE=acos(-1.0);
 24 const int d1x[]= {0,-1,0,1};
 25 const int d1y[]= {-1,0,1,0};
 26 const int d2x[]= {0,-1,0,1};
 27 const int d2y[]= {1,0,-1,0};
 28 const int fx[]= {-1,-1,-1,0,0,1,1,1};
 29 const int fy[]= {-1,0,1,-1,1,-1,0,1};
 30 /***************************************/
 31 void openfile()
 32 {
 33     freopen("data.in","rb",stdin);
 34     freopen("data.out","wb",stdout);
 35 }
 36 /**********************华丽丽的分割线,以上为模板部分*****************/
 37 char map[100][100];
 38 int sum1,sum2,sum3;
 39 int sum11,sum22;
 40 int ex,ey;
 41 int w,h;
 42 int vis[100][100],cnt[100][100];
 43 
 44 void zuo(int x,int y,int d)
 45 {
 46     int i,j;
 47     if (x==ex&&y==ey)
 48     {
 49         sum11=sum1;
 50         return ;
 51     }
 52     if (d==1)
 53         d=0;
 54     else if (d==2)
 55         d=1;
 56     else if (d==3)
 57         d=2;
 58     else if (d==0)
 59         d=3;
 60     for(i=d;i<4;i++)
 61     {
 62         if (x+d1x[i]<h&&x+d1x[i]>=0&&y+d1y[i]<w&&y+d1y[i]>=0&&map[x+d1x[i]][y+d1y[i]]!=‘#‘)
 63         {
 64             sum1++;
 65             zuo(x+d1x[i],y+d1y[i],i);
 66         }
 67         if (sum11)
 68            return ;
 69         if (i==3)
 70             i=-1;
 71     }
 72 
 73 
 74 
 75 
 76     /*if (x==ex&&y==ey)
 77         return ;
 78     if (y-1>=0&&map[x][y-1]==‘.‘)
 79     {
 80         sum1++;
 81         zuo(x,y-1);
 82     }
 83     else if (x-1>=0&&map[x-1][y]==‘.‘)
 84     {
 85         sum1++;
 86         zuo(x-1,y);
 87     }
 88     else if (y+1<w&&map[x][y+1]==‘.‘)
 89     {
 90         sum1++;
 91         zuo(x,y+1);
 92     }
 93     else if (x+1<h&&map[x+1][y]==‘.‘)
 94     {
 95         sum1++;
 96         zuo(x+1,y);
 97     } */
 98 }
 99 void you(int x,int y,int d)
100 {
101     int i,j;
102     if (x==ex&&y==ey)
103     {
104         sum22=sum2;
105         return ;
106     }
107     if (d==1)
108         d=0;
109     else if (d==2)
110         d=1;
111     else if (d==3)
112         d=2;
113     else if (d==0)
114         d=3;
115     for(i=d;i<4;i++)
116     {
117         if (x+d2x[i]<h&&x+d2x[i]>=0&&y+d2y[i]<w&&x+d2y[i]>=0&&map[x+d2x[i]][y+d2y[i]]!=‘#‘)
118         {
119             sum2++;
120             you(x+d2x[i],y+d2y[i],i);
121         }
122         if (sum22)
123             return ;
124         if (i==3)
125             i=-1;
126     }
127 
128 
129 
130 
131     /*if (x==ex&&y==ey)
132         return ;
133     if (y+1>=0&&map[x][y+1]==‘.‘)
134     {
135         sum1++;
136         you(x,y+1);
137     }
138     else if (x-1>=0&&map[x-1][y]==‘.‘)
139     {
140         sum1++;
141         you(x-1,y);
142     }
143     else if (y-1<w&&map[x][y-1]==‘.‘)
144     {
145         sum1++;
146         you(x,y-1);
147     }
148     else if (x+1<h&&map[x+1][y]==‘.‘)
149     {
150         sum1++;
151         you(x+1,y);
152     } */
153 }
154 int BFS(int x,int y)
155 {
156     queue<int >Q;
157     Q.push(x);
158     Q.push(y);
159     int v1,v2;
160     while(!Q.empty())
161     {
162         v1=Q.front();
163         Q.pop();
164         v2=Q.front();
165         Q.pop();
166         if (vis[v1][v2]==-1)
167             continue;
168         if (v1==ex&&v2==ey)
169         {
170             sum3=cnt[v1][v2];
171             return 0;
172         }
173         vis[v1][v2]=-1;
174         if (v1>=0&&v1<h&&v2>=0&&v2<w)
175         {
176             if (v1-1>=0&&map[v1-1][v2]!=‘#‘)
177             {
178                 Q.push(v1-1);
179                 Q.push(v2);
180                 cnt[v1-1][v2]=cnt[v1][v2]+1;
181             }
182             if (v1+1<h&&map[v1+1][v2]!=‘#‘)
183             {
184                 Q.push(v1+1);
185                 Q.push(v2);
186                 cnt[v1+1][v2]=cnt[v1][v2]+1;
187             }
188             if (v2-1>=0&&map[v1][v2-1]!=‘#‘)
189             {
190                 Q.push(v1);
191                 Q.push(v2-1);
192                 cnt[v1][v2-1]=cnt[v1][v2]+1;
193             }
194             if (v2+1<w&&map[v1][v2+1]!=‘#‘)
195             {
196                 Q.push(v1);
197                 Q.push(v2+1);
198                 cnt[v1][v2+1]=cnt[v1][v2]+1;
199             }
200         }
201     }
202     return 0;
203 }
204 int main()
205 {
206 
207     int cas;
208     scanf("%d",&cas);
209     while(cas--)
210     {
211         memset(map,0,sizeof(map));
212         memset(vis,0,sizeof(vis));
213         memset(cnt,0,sizeof(cnt));
214         scanf("%d%d",&w,&h);
215         int i,j;
216         int sx,sy;
217         sum1=0;sum2=0;sum3=0;
218         sum11=0;sum22=0;
219         for(i=0;i<h;i++)
220         {
221             getchar();
222             for(j=0;j<w;j++)
223             {
224                 scanf("%c",&map[i][j]);
225                 if (map[i][j]==‘S‘)
226                 {
227                     sx=i;
228                     sy=j;
229                 }
230                 if (map[i][j]==‘E‘)
231                 {
232                     ex=i;
233                     ey=j;
234                 }
235             }
236         }
237         zuo(sx,sy,1);
238         you(sx,sy,1);
239         BFS(sx,sy);
240         printf("%d %d %d\n",sum11+1,sum22+1,sum3+1);
241     }
242     return 0;
243 }