Lightoj 1066 - Gathering Food

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

1. #include <bits/stdc++.h>
2. using namespace std;
3. string grid[12];
4. bool vis[12][12];
5. int dis[12][12];
6. int dx[] = {0, 0, +1, -1};
7. int dy[] = {+1, -1, 0, 0};
8. int n;
9. bool valid(int x, int y, char ch){
10.     if(x<0 || x == n || y<0||y == n || grid[x][y] == '#') return false;
11.     else if(grid[x][y]>= 'A'&& grid[x][y]<= 'Z' && grid[x][y]  > ch+1) return false;
12.     return true;
13. }
14. int bfs(char ch, int x, int y){
15.     list< pair<int, int> >q;
16.     q.push_back(make_pair(x, y));
17.     vis[x][y]= true;
18.     dis[x][y] = 0;
19.     while(!q.empty()){
20.         int fromx = q.front().first;
21.         int fromy = q.front().second;
22.         vis[fromx][fromy] = true;
23.         q.pop_front();
24.         for(int i = 0; i < 4; i++){
25.             int tox = fromx + dx[i];
26.             int toy = fromy + dy[i];
27.             if(!valid(tox, toy, ch)) continue;
28.             if(vis[tox][toy]) continue;
29.             vis[tox][toy] = true;
30.             q.push_back(make_pair(tox, toy));
31.             dis[tox][toy] = dis[fromx][fromy] + 1;
32.             if(grid[tox][toy] == ch+1) return dis[tox][toy];
33.         }
34.     }
35.     return -1;
36. }
37. int main(){
38.     int ts;
39.     scanf("%d", &ts);
40.     for(int p = 1; p <= ts; p++){
41.     memset(vis, false, sizeof(vis));
42.     memset(dis, false, sizeof(dis));
43.     scanf("%d", &n);
44.     int co = 0;
45.     pair<int,int> positions[26];
46.     for(int i = 0; i <n; i++){
47.         //scanf("%s", grid[i]);
48.         cin>>grid[i];
49.         for(int j = 0; j <grid[i].size(); j++){
50.             if(grid[i][j]>= 'A' && grid[i][j]<= 'Z'){
51.                 positions[grid[i][j]-'A'].first = i;
52.                 positions[grid[i][j]-'A'].second = j;
53.                 co++;
54.             }
55.         }
56.     }
57.     int sum = 0;
58.     for(int i = 0; i <co-1; i++){
59.         int val = bfs('A'+i, positions[i].first, positions[i].second);
60.         if(val == -1) {
61.             sum = -1;
62.             break;
63.         }
64.         sum+= val;
65.         memset(vis, false, sizeof(vis));
66.         memset(dis, false, sizeof(dis));
67.        
68.     }
69.     if(sum == -1) printf("Case %d: Impossible\n", p);
70.     else printf("Case %d: %d\n",p, sum);
71.     }
72.     return 0;
73. }
74.