LightOJ - 1238 - Power Puff Girls

1. /****************#####    بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم  #####*******************
2. __________________________________________________________________________
3. ######################  Ya-Seen Arafat(ACWizard) #########################
4. ######################        UAP-CSE-33B        #########################
5. *************************************************************************/
6. #include <bits/stdc++.h>
7. #define sc(n) scanf("%d", &n)
8. #define scS(n) scanf("%s", n)
9. #define S 23
10. using namespace std;
11. typedef long long LL;
12.  
13. int dirX[] = {1, 0, -1, 0, 1, -1, 1, -1};
14. int dirY[] = {0, 1, 0, -1, 1, -1, -1, 1};
15.  
16. struct node{
17.     int x, y;
18.     node(int p, int q){
19.         x = p, y = q;
20.     }
21. };
22.  
23. char cell[S][S];
24. int dist[S][S];
25. int n, m;
26.  
27. int bfs(int u, int v){
28.     queue <node> Qu;
29.     memset(dist, -1, sizeof(dist));
30.     Qu.push(node(u, v));
31.     dist[u][v] = 0;
32.     while(!Qu.empty()){
33.         node i = Qu.front(); Qu.pop();
34.         for(int z = 0; z < 4; z++){
35.             int I = i.x+dirX[z], J = i.y+dirY[z];
36.             if(dist[I][J] != -1 || cell[I][J] == '#' || cell[I][J] == 'm')continue;
37.             if(I >= n || J >= m || I < 0 || J < 0)continue;
38.             dist[I][J] = dist[i.x][i.y]+1;
39.             if(cell[I][J] == 'h')return dist[I][J];
40.             Qu.push(node(I, J));
41.         }
42.     }
43. }
44.  
45. void Do(){
46.     int t, cs = 0;
47.     sc(t);
48.     while(t--){
49.         sc(n); sc(m);
50.         for(int i = 0; i < n; i++)scS(cell[i]);
51.         int mx = -INT_MAX;
52.         for(int i = 0; i < n; i++){
53.             for(int j = 0; j < m; j++){
54.                 if(cell[i][j] == 'a' || cell[i][j] == 'b' || cell[i][j] == 'c'){
55.                     int x = bfs(i, j);
56.                     mx = max(mx, x);
57.                 }
58.             }
59.         }
60.         printf("Case %d: %d\n", ++cs, mx);
61.     }
62. }
63.  
64. int main(){
65.     ios_base::sync_with_stdio(0); cin.tie(0);
66.     #ifndef ONLINE_JUDGE
67.     ///freopen("inp","r",stdout);
68.     ///freopen("contest.txt","w",stdout);
69.     #endif
70.     Do();
71.     return 0;
72. }