loj 1337
10332 ワード
タイトルリンク:http://lightoj.com/volume_showproblem.php?problem=1337
考え方:検索した領域をマークし、要求された点が検索した領域に落ちたら、直接取り出せばいい.そうしないと、dfsにしてください.
View Code
考え方:検索した領域をマークし、要求された点が検索した領域に落ちたら、直接取り出せばいい.そうしないと、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:
", 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
", cnt);
56 }
57 else {
58 printf("%d
", ans[mark[x][y]]);
59 }
60 }
61 }
62 return 0;
63 }View Code