Submission #41024

ソースコード

?
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
import java.io.*;
import java.util.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
class Main {
private final static PrintWriter out = new PrintWriter(System.out);
private final static int dx[] = { 1, 0, -1, 0 };
private final static int dy[] = { 0, 1, 0, -1 };
private final void solve() {
char[][] mas = new char[1005][];
int[][] id = new int[1002][1002];
int H, W, Q;
H=nu(); W=nu(); Q=nu();
{
int cnt = 0;
for (int i=0; i<H; ++i) {
mas[i] = ns().toCharArray();
for (int j=0; j<W; ++j) id[i][j] = cnt++;
}
}
UnionFind uf = new UnionFind((H+1) * (W+1));
for (int i=0; i<H; ++i) {
for (int j=0; j<W; ++j) {
if (mas[i][j] == '#') {
if (j+1 < W && mas[i][j+1] == '#')
uf.unite(id[i][j], id[i][j+1]);
if (i+1 < H && mas[i+1][j] == '#')
uf.unite(id[i][j], id[i+1][j]);
}
}
}
while (Q-- > 0) {
int op, y, x;
op=nu();
y = nu()-1;
x = nu()-1;
if (op == 0) {
mas[y][x] = '#';
for (int i=0; i<4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx<0 || ny<0 || nx>=W || ny>=H || mas[ny][nx] != '#') continue;
uf.unite(id[y][x], id[ny][nx]);
}
}
else {
out.println( (mas[y][x] == '#')? uf.size(id[y][x]) : 0 );
}
}
}
public static void main(String[] args) {
new Main().solve();
out.close();
}
private static final class UnionFind
{
private int[] uni;
UnionFind(int n) {
uni = new int[n+5];
fill(uni, -1);
}
int root(int x) {
if (uni[x] < 0) return x;
return (uni[x] = root(uni[x]));
}
void unite(int x, int y) {
x=root(x); y=root(y);
if (x == y) return;
if (uni[y] < uni[x]) {
int tmp = x; x = y; y = tmp;
}
uni[x] += uni[y];
uni[y] = x;
}
int size(int i) { return -uni[root(i)]; }
}
//=====================================================================
private static final InputStream in = System.in;
private static final byte[] buf = new byte[1 << 14];
private static int bufP = 0;
private static int bufLen = 0;
private static final boolean hasNext() {
if(bufP >= bufLen) {
bufP = 0;
try {
bufLen = in.read(buf);
} catch (IOException e) { e.printStackTrace(); }
}
return (bufP < bufLen);
}
private static final int ni() { return (int)nl(); }
private static final int nc() { return hasNext()? buf[bufP++] : -1; }
private static final int nu() {
int ret = 0, c;
while ((c=nc()) <= 32);
while (c >= '0') {
ret = ret*10 + c-'0';
c = nc();
}
return (ret);
}
private static final long nl() {
boolean minus = false;
int c;
long ret=0;
while ((c=nc()) <= 32);
if (c == '-') {
minus = true;
c = nc();
}
while (c >= '0') {
ret = ret*10 + c-'0';
c = nc();
}
return minus ? -ret : ret;
}
private static final String ns() {
final StringBuilder sb = new StringBuilder();
int c;
while ((c=nc()) <= 32 && c != -1);
if (c == -1)return null;
while (c > 32) {
sb.appendCodePoint(c);
c = nc();
}
return sb.toString();
}
}

ステータス

項目 データ
問題 0971 - 島の創造
ユーザー名 Arumakan_ei1727
投稿日時 2018-08-09 19:19:40
言語 Java
状態 Accepted
得点 10
ソースコード長 4139 Byte
最大実行時間 282 ms
最大メモリ使用量 42236 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input-sample1 AC 100 ms 18660 KB
1
2
input-sample2 AC 104 ms 19240 KB
1
2
input01-easy AC 100 ms 18812 KB
1
2
input02-easy AC 93 ms 18640 KB
1
2
input03-easy AC 94 ms 18820 KB
1
2
input04 AC 238 ms 31464 KB
2
input05 AC 204 ms 26748 KB
2
input06 AC 228 ms 27076 KB
2
input07 AC 235 ms 27756 KB
2
input08 AC 232 ms 37256 KB
2
input09 AC 282 ms 36936 KB
2
input10 AC 263 ms 37736 KB
2
input11 AC 281 ms 42164 KB
2
input12 AC 207 ms 42236 KB
2
input13 AC 100 ms 30220 KB
2
input14 AC 92 ms 30676 KB
2