Submission #41279

ソースコード

?
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] == '#'){
cout << tree[root(i,j)].size << endl;
}else{
cout << 0 << endl;
}
}
}
return 0;
}

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input-sample1 AC 31 ms 2528 KB
1
2
input-sample2 AC 23 ms 2500 KB
1
2
input01-easy AC 35 ms 2596 KB
1
2
input02-easy AC 26 ms 2724 KB
1
2
input03-easy AC 32 ms 2844 KB
1
2
input04 AC 519 ms 10392 KB
2
input05 AC 360 ms 10800 KB
2
input06 AC 501 ms 11832 KB
2
input07 AC 554 ms 12812 KB
2
input08 AC 593 ms 14108 KB
2
input09 AC 604 ms 15752 KB
2
input10 AC 624 ms 16496 KB
2
input11 AC 1065 ms 20316 KB
2
input12 AC 569 ms 20800 KB
2
input13 AC 25 ms 13996 KB
2
input14 AC 17 ms 13972 KB
2