题目链接:http://lightoj.com/volume_showproblem.php?problem=1337
思路:对于搜过的区域进行标记,如果要求的点落在已经搜过的区域,那么直接取出来即可,否则,就dfs一下。
1 #define _CRT_SECURE_NO_WARNINGS 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 #include <queue> 7 using namespace std; 8 9 const int MAXN = (500 + 50); 10 int n, m, Q, _count, cnt; 11 char map[MAXN][MAXN]; 12 int mark[MAXN][MAXN]; 13 vector<int >ans; 14 int dir[4][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1} }; 15 16 void dfs(int x, int y) 17 { 18 mark[x][y] = _count; 19 if (map[x][y] == ‘C‘) cnt++; 20 for (int i = 0; i < 4; i++) { 21 int xx = x + dir[i][0]; 22 int yy = y + dir[i][1]; 23 if (xx >= 0 && xx < n && yy >= 0 && yy < m && map[xx][yy] != ‘#‘) { 24 if (mark[xx][yy] == -1)dfs(xx, yy); 25 } 26 } 27 } 28 29 30 int main() 31 { 32 int _case, t = 1; 33 scanf("%d", &_case); 34 while (_case--) { 35 scanf("%d %d %d", &n, &m, &Q); 36 for (int i = 0; i < n; i++) { 37 scanf("%s", map[i]); 38 } 39 memset(mark, -1, sizeof(mark)); 40 ans.clear(); 41 _count = -1; 42 printf("Case %d:\n", t++); 43 while (Q--) { 44 int x, y; 45 scanf("%d %d", &x, &y); 46 x--, y--; 47 if (map[x][y] == ‘#‘) { 48 puts("0"); 49 } 50 else if (mark[x][y] == -1) { 51 _count++; 52 cnt = 0; 53 dfs(x, y); 54 ans.push_back(cnt); 55 printf("%d\n", cnt); 56 } 57 else { 58 printf("%d\n", ans[mark[x][y]]); 59 } 60 } 61 } 62 return 0; 63 }