Submission #41030

ソースコード

?
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
144
145
146
147
148
import java.io.*;
import java.util.*;
public class Main{
static FastScanner s=new FastScanner(System.in);
static int h =s.nextInt();
static int w =s.nextInt();
static int q =s.nextInt();
static char[][] f=new char[h][w];
static UF uf=new UF(h*w);
public static void main(String[] $){
for(int i=0;i<h;++i)
s.next().getChars(0,w,f[i],0);
System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
for(int i=0;i<h;++i)
for(int j=0;j<w;++j)
if(f[i][j]=='#')
island(i,j);
for(;q>0;--q){
int m=s.nextInt();
int i=s.nextInt()-1;
int j=s.nextInt()-1;
if(m==0)
island(i,j);
else
System.out.println(f[i][j]!='#'?0:uf.groupSize(i*w+j));
}
System.out.flush();
}
static int[] dx={0,1,0,-1},dy={1,0,-1,0};
static void island(int i,int j){
f[i][j]='#';
for(int d=0;d<4;++d){
int I=i+dy[d],J=j+dx[d];
if(0<=I&&I<h&&0<=J&&J<w
&&f[I][J]=='#')
uf.connect(i*w+j,I*w+J);
}
}
}
class UF{
public int[] uni;
public UF(int size){
Arrays.fill(uni=new int[size],-1);
}
public int root(int t){
return uni[t]<0?t:(uni[t]=root(uni[t]));
}
/** @return changed */
public boolean connect(int a,int b){
if((a=root(a))==(b=root(b)))
return false;
if(uni[a]>uni[b]){
int buf=b;
b=a;
a=buf;
}
uni[a]+=uni[b];
uni[b]=a;
return true;
}
public boolean connected(int a,int b){
return root(a)==root(b);
}
public int groupSize(int t){
return -uni[root(t)];
}
}
class FastScanner{
private final BufferedInputStream in;
private static final int bufSize =1<<16;
private final byte buf[] =new byte[bufSize];
private int i =bufSize,k=bufSize;
private final StringBuilder str =new StringBuilder();
FastScanner(InputStream in){
this.in=new BufferedInputStream(in,bufSize);
}
int nextInt(){
return (int)nextLong();
}
long nextLong(){
int c;
long x=0;
boolean sign=true;
while((c=nextChar())<=32)
;
if(c=='-'){
sign=false;
c=nextChar();
}
if(c=='+'){
c=nextChar();
}
while(c>='0'){
x=x*10+(c-'0');
c=nextChar();
}
return sign?x:-x;
}
private int nextChar(){
if(i==k){
try{
k=in.read(buf,i=0,bufSize);
}catch(IOException e){
System.exit(-1);
}
}
return i>=k?-1:buf[i++];
}
String next(){
int c;
str.setLength(0);
while((c=nextChar())<=32&&c!=-1)
;
if(c==-1)
return null;
while(c>32){
str.append((char)c);
c=nextChar();
}
return str.toString();
}
String nextLine(){
int c;
str.setLength(0);
while((c=nextChar())<=32&&c!=-1)
;
if(c==-1)
return null;
while(c!='\n'){
str.append((char)c);
c=nextChar();
}
return str.toString();
}
}

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input-sample1 AC 92 ms 13032 KB
1
2
input-sample2 AC 100 ms 12948 KB
1
2
input01-easy AC 109 ms 12728 KB
1
2
input02-easy AC 88 ms 12860 KB
1
2
input03-easy AC 104 ms 12608 KB
1
2
input04 AC 245 ms 22308 KB
2
input05 AC 223 ms 22024 KB
2
input06 AC 233 ms 21960 KB
2
input07 AC 250 ms 22832 KB
2
input08 AC 247 ms 27668 KB
2
input09 AC 260 ms 29156 KB
2
input10 AC 255 ms 29544 KB
2
input11 AC 351 ms 33828 KB
2
input12 AC 228 ms 33792 KB
2
input13 AC 91 ms 23912 KB
2
input14 AC 95 ms 26140 KB
2