Lightoj 1238 - Power Puff Girls

http://lightoj.com/volume_showproblem.php?problem=1238

1. #include <bits/stdc++.h>
2. using namespace std;
3. int m, n;
4. string grid[21];
5. bool vis[21][21];
6. int dx[] = {0, 0, 1, -1};
7. int dy[] = {1, -1, 0, 0};
8. int dis[21][21];
9. bool valid(int i, int j){
10.     if(i<0 && i >=n && j <0 && j >=m) return false;
11.     if(grid[i][j] == 'm' || grid[i][j] == '#') return false;
12.     return true;
13. }
14.  
15. void bfs( pair<int, int> s){
16.     memset(vis,false, sizeof(vis));
17.     memset(dis, 0, sizeof(dis));
18.     list< pair<int, int> >q;
19.     q.push_back(s);
20.     vis[s.first][s.second]= true;
21.     dis[s.first][s.second] = 0;
22.     while(!q.empty()){
23.         pair <int, int> from = q.front();
24.         vis[from.first][from.second] = true;
25.         q.pop_front();
26.         for(int i = 0; i <4; i++){
27.             pair<int, int> to;
28.             to.first = from.first + dx[i];
29.             to.second = from.second + dy[i];
30.             if(!valid(to.first, to.second)) continue;
31.             if(vis[to.first][to.second]) continue;
32.             vis[to.first][to.second] = true;
33.             q.push_back(to);
34.             dis[to.first][to.second] = dis[from.first][from.second] + 1;
35.         }
36.     }
37. }
38.  
39. int main(){
40.     int ts;
41.     scanf("%d", &ts);
42.     for(int p= 1; p <=ts; p++){
43.     pair <int, int> a, b, c, h;
44.     scanf("%d%d", &n,&m);
45.     for(int i = 0; i <n; i++){
46.             //scanf("%s", grid[i]);
47.             cin>>grid[i];
48.             for(int j = 0; j <grid[i].length(); j++){
49.             if(grid[i][j] == 'a') {
50.                 a.first = i;
51.                 a.second = j;
52.             }
53.             if(grid[i][j] == 'b') {
54.                 b.first = i;
55.                 b.second = j;
56.             }
57.             if(grid[i][j] == 'c') {
58.                 c.first = i;
59.                 c.second = j;
60.             }
61.             if(grid[i][j] == 'h') {
62.                 h.first = i;
63.                 h.second = j;
64.             }
65.             }
66.     }
67.     /*
68.     for(int i = 0; i <n; i++){
69.         cout<<grid[i]<<endl;
70.         //cout<<endl;
71.     }
72.     */
73.     bfs(h);
74.     int ans = max(max(dis[a.first][a.second], dis[b.first][b.second]),dis[c.first][c.second] );
75.     printf("Case %d: %d\n", p, ans);
76.     /*
77.     cout<<endl;
78.     for(int i = 0; i <n; i++){
79.         for(int j = 0; j <m; j++){ 
80.             cout<<dis[i][j]<<" ";
81.         }
82.         cout<<endl;
83.     }
84.     */
85.     }
86.     return 0;
87. }