Submission #41278

ソースコード

?
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
#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;
tree[x] = tree[root2(tree[x].root)];
return tree[x].root;
}
int root(int i,int j){
if(tree[i*w+j].root == i*w+j) return i*w+j;
tree[i*w+j] = tree[root2(tree[i*w+j].root)];
return 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))].size = tree[min(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] == '#'){
cout << tree[root(i,j)].size << endl;
}else{
cout << 0 << endl;
}
}
}
return 0;
}

ステータス

項目 データ
問題 0971 - 島の創造
ユーザー名 ei1719
投稿日時 2018-08-13 21:17:43
言語 C++11
状態 Accepted
得点 10
ソースコード長 1970 Byte
最大実行時間 1127 ms
最大メモリ使用量 20780 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input-sample1 AC 26 ms 2528 KB
1
2
input-sample2 AC 22 ms 2500 KB
1
2
input01-easy AC 29 ms 2600 KB
1
2
input02-easy AC 22 ms 2600 KB
1
2
input03-easy AC 22 ms 2844 KB
1
2
input04 AC 566 ms 10396 KB
2
input05 AC 377 ms 10800 KB
2
input06 AC 530 ms 11820 KB
2
input07 AC 583 ms 12668 KB
2
input08 AC 627 ms 14216 KB
2
input09 AC 682 ms 15600 KB
2
input10 AC 627 ms 16348 KB
2
input11 AC 1127 ms 20288 KB
2
input12 AC 600 ms 20780 KB
2
input13 AC 22 ms 13716 KB
2
input14 AC 28 ms 13944 KB
2