Submission #41722

ソースコード

?
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
#include <bits/stdc++.h>
using namespace std;
typedef struct{
int root;
int size;
} Tree;
int h,w,q;
char mp[1010][1010];
Tree tree[1010*1010];
void init(){
for(int i = 0;i < h;i++){
for(int j = 0;j < w;j++){
tree[i*w+j].root = i*w+j;
tree[i*w+j].size = 1;
}
}
return;
}
int root2(int x){
if(tree[x].root == x) return x;
return tree[x].root = root2(tree[x].root);
}
int root(int i,int j){
if(tree[i*w+j].root == i*w+j) return i*w+j;
return tree[i*w+j].root = root2(tree[i*w+j].root);
}
void unit(int i1,int j1,int i2,int j2){
if(root(i1,j1) != root(i2,j2)){
tree[min(root(i1,j1),root(i2,j2))].size += tree[max(root(i1,j1),root(i2,j2))].size;
tree[max(root(i1,j1),root(i2,j2))].root = tree[min(root(i1,j1),root(i2,j2))].root;
}
return;
}
int main(){
scanf("%d %d %d", &h, &w, &q);
init();
for(int i = 0;i < h;i++){
scanf("%s",mp[i]);
}
for(int i = 0;i < h;i++){
for(int j = 0;j < w;j++){
if(mp[i][j] == '#'){
if(j < w-1 && mp[i][j+1] == '#') unit(i,j,i,j+1);
if(j > 0 && mp[i][j-1] == '#') unit(i,j,i,j-1);
if(i < h-1 && mp[i+1][j] == '#') unit(i,j,i+1,j);
if(i > 0 && mp[i-1][j] == '#') unit(i,j,i-1,j);
}
}
}
int p,i,j;
for(int x = 0;x < q;x++){
scanf("%d %d %d", &p, &i, &j);
i--;
j--;
if(p == 0){
mp[i][j] = '#';
if(j < w-1 && mp[i][j+1] == '#') unit(i,j,i,j+1);
if(j > 0 && mp[i][j-1] == '#') unit(i,j,i,j-1);
if(i < h-1 && mp[i+1][j] == '#') unit(i,j,i+1,j);
if(i > 0 && mp[i-1][j] == '#') unit(i,j,i-1,j);
}else{
if(mp[i][j] == '#'){
printf("%d\n",tree[root(i,j)].size);
}else{
printf("0\n");
}
}
}
return 0;
}

ステータス

項目 データ
問題 0971 - 島の創造
ユーザー名 ei1719
投稿日時 2018-08-23 22:01:32
言語 C++11
状態 Accepted
得点 10
ソースコード長 1836 Byte
最大実行時間 224 ms
最大メモリ使用量 44344 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input-sample1 AC 28 ms 2528 KB
1
2
input-sample2 AC 22 ms 2492 KB
1
2
input01-easy AC 25 ms 2588 KB
1
2
input02-easy AC 24 ms 2600 KB
1
2
input03-easy AC 22 ms 2840 KB
1
2
input04 AC 224 ms 14108 KB
2
input05 AC 108 ms 16696 KB
2
input06 AC 171 ms 21304 KB
2
input07 AC 156 ms 26380 KB
2
input08 AC 172 ms 32540 KB
2
input09 AC 145 ms 33788 KB
2
input10 AC 182 ms 35176 KB
2
input11 AC 198 ms 39120 KB
2
input12 AC 155 ms 44344 KB
2
input13 AC 19 ms 37408 KB
2
input14 AC 24 ms 37508 KB
2