Lightoj 1066 Gathering Food（BFS）

题目链接：
http://lightoj.com/volume_showproblem.php?problem=1066
题目很容易，广搜和深搜应该都行，我个人认为要注意的是‘A’-->‘ . ’
AC代码：
 1 #include <iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include <cstring>
 5 using namespace std;
 6 char s[20][20],ch[50];
 7 int t,n,fine,starex,starey,sum,flag;
 8 struct node
 9 {
10     int x,y,f;
11 };
12 int main()
13 {
14     struct node que[2005];
15     int book[20][20];
16     int a[4]={1,-1,0,0},b[4]={0,0,1,-1};
17     int head,tail,tx,ty;
18     strcpy(ch,"ABCDEFGHIJKLMNOPQRSTUVWXYZ");
19     while(~scanf("%d",&t))
20     {
21         for(int v=1;v<=t;v++)
22         {
23             scanf("%d",&n);
24             for(int i=0;i<n;i++)
25             scanf("%s",s[i]);
26             fine=0;
27             for(int i=0;i<n;i++)
28             {
29                 for(int j=0;j<n;j++)
30                 {
31                     if(s[i][j]>='A'&&s[i][j]<='Z')
32                     {
33                         fine=max(s[i][j]-'A',fine);
34                         if(s[i][j]=='A')
35                         {
36                             starex=i;starey=j;
37                             s[i][j]='.';
38                         }
39                     }
40                 }
41             }
42             flag=0;sum=0;
43             head=1;tail=1;
44             memset(que,0,sizeof(que));
45             que[tail].x=starex;que[tail].y=starey;
46             que[tail].f=0;tail++;
47             memset(book,0,sizeof(book));
48             book[starex][starey]=1;
49             while(head<tail)
50             {
51                 for(int k=0;k<4;k++)
52                 {
53                     tx=que[head].x+a[k];
54                     ty=que[head].y+b[k];
55                     if(tx<0||tx>=n||ty<0||ty>=n)
56                     continue;
57                     if((s[tx][ty]=='.'||s[tx][ty]==ch[flag+1])&&book[tx][ty]==0)
58                     {
59                         book[tx][ty]=1;
60                         que[tail].x=tx;
61                         que[tail].y=ty;
62                         que[tail].f=que[head].f+1;
63                         tail++;
64                     }
65                     if(s[tx][ty]==ch[flag+1])
66                     {
67                         s[tx][ty]='.';
68                         flag++;
69                         sum=sum+que[tail-1].f;
70                         head=0;tail=1;
71                         memset(que,0,sizeof(que));
72                         que[tail].x=tx;que[tail].y=ty;
73                         que[tail].f=0;
74                         memset(book,0,sizeof(book));
75                         book[tx][ty]=1;
76                         tail++;
77                         break;
78                     }
79                 }
80                 if(flag==fine)
81                 break;
82                 head++;
83             }
84             printf("Case %d: ",v);
85             if(flag==fine)
86             printf("%d
",sum);
87             else
88             printf("Impossible
");
89         }
90     }
91     return 0;
92 }
View Code