1012 - Guilty Prince (Light OJ)

1. #include<iostream>
2. #include<cstdio>
3. #include<cmath>
4. #include<queue>
5. #include<cstring>
6. using namespace std;
7. typedef pair<int,int> pii;
8. #define pf printf
9. #define sf scanf
10. #define MAX 1000
11.  
12. char grid[50][50];
13. bool vis[50][50];
14. queue <pii> Q;
15. int r , c;
16. int dx[] = {0, 0, -1, 1};
17. int dy[] = {-1, 1, 0, 0};
18.  
19. bool valid(int x,int y)
20. {
21.     return x>=0 && y>=0 && x<r && y<c && (grid[x][y]=='.');
22. }
23. int bfs(int x, int y)
24. {
25.     int ux, uy, vx, vy, cnt=0;
26.     memset(vis, 0, sizeof(vis));
27.     while(!Q.empty()) Q.pop(); //queue clear
28.  
29.     vis[x][y] =  true;
30.     Q.push(pii(x,y));
31.  
32.     while(!Q.empty())
33.     {
34.         pii u = Q.front(); Q.pop();
35.         ux = u.first; uy = u.second;
36.         for(int i=0; i<4 ;i++)
37.         {
38.             vx = ux + dx[i];
39.             vy = uy + dy[i];
40.             if(!valid(vx, vy)) continue;
41.             if(vis[vx][vy]) continue;
42.             cnt++;
43.             vis[vx][vy] = true;
44.             Q.push(make_pair(vx, vy));
45.         }
46.     }
47.     return cnt;
48. }
49. int main()
50. {
51.     //freopen("in.txt", "r", stdin);
52.     int sr, sc, kase=0;
53.     int test, t;
54.     int i, j;
55.     sf("%d", &test);
56.     while(test--)
57.     {
58.         sf("%d%d", &c, &r);
59.         for(i=0; i<r; i++)
60.             sf("%s", grid[i]);
61.  
62.         for(i=0; i<r; i++)
63.             for(j=0; j<c; j++)
64.                 if(grid[i][j]=='@')
65.                     sr = i , sc = j, i = j = c+r;
66.  
67.         int ans =  bfs(sr, sc)+1;
68.         pf("Case %d: %d\n", ++kase, ans);
69.     }
70.     return 0;
71. }
72.