Submission #41023

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <stdio.h>
#include <string.h>
#define MAX_H (1005)
#define MAX_W (1005)
int tree[MAX_H * MAX_W];
char mp[MAX_H][MAX_W];
int h, w;
int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
void link_island(int y, int x, char map[MAX_H][MAX_W]);
void unite(int a, int b);
int root(int x);
int what_size(int y, int x);
int main()
{
memset(tree, -1, sizeof(tree));
int q;
int query, y, x;
int i, j, k;
scanf("%d %d %d", &h, &w, &q);
for (i = 0; i < h; ++i) {
scanf("%s", mp[i]);
}
for (i = 0; i < h; ++i) {
for (j = 0; j < w; ++j) {
link_island(i, j, mp);
}
}
for (i = 0; i < q; ++i) {
scanf("%d %d %d", &query, &y, &x);
--y; --x;
if (query == 0) {
mp[y][x] = '#';
link_island(y, x, mp);
} else {
printf("%d\n", (mp[y][x] == '#' ? what_size(y, x) : 0));
}
}
return 0;
}
void link_island(int y, int x, char map[MAX_H][MAX_W])
{
int i;
if (map[y][x] == '#') {
for (i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if ((ny >= 0 && ny < h) &&
(nx >= 0 && nx < w) &&
map[ny][nx] == '#') {
unite(y * MAX_H + x, ny * MAX_H + nx);
}
}
}
return;
}
void unite(int a, int b)
{
a = root(a);
b = root(b);
if (a != b) {
tree[a] += tree[b];
tree[b] = a;
}
return;
}
int root(int x)
{
if (tree[x] < 0) return x;
return tree[x] = root(tree[x]);
//経路圧縮を忘れた雑魚
}
int what_size(int y, int x)
{
return tree[root(y * MAX_H + x)] * -1;
}

ステータス

項目 データ
問題 0971 - 島の創造
ユーザー名 ei1710
投稿日時 2018-08-09 18:15:28
言語 C(gnu99)
状態 Accepted
得点 10
ソースコード長 1821 Byte
最大実行時間 178 ms
最大メモリ使用量 16520 KB

セット

セット 得点 Cases
1 Easy 1 / 1 *easy, *sample*
2 ALL 9 / 9 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input-sample1 AC 24 ms 4320 KB
1
2
input-sample2 AC 26 ms 4264 KB
1
2
input01-easy AC 20 ms 4328 KB
1
2
input02-easy AC 22 ms 4320 KB
1
2
input03-easy AC 25 ms 4432 KB
1
2
input04 AC 165 ms 6152 KB
2
input05 AC 107 ms 6696 KB
2
input06 AC 149 ms 7612 KB
2
input07 AC 163 ms 8600 KB
2
input08 AC 153 ms 10040 KB
2
input09 AC 178 ms 11312 KB
2
input10 AC 146 ms 12064 KB
2
input11 AC 174 ms 16020 KB
2
input12 AC 118 ms 16520 KB
2
input13 AC 19 ms 15608 KB
2
input14 AC 25 ms 15688 KB
2