Submission #00150

ソースコード

?
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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
#include<bits/stdc++.h>
using namespace std;
struct P{
int y,x;
};
int h,w,n;
char maps[1005][1005];
int dat[10005];
int wake[1005][1005];
int checks[1005][1005];
int dy[] = {-1,-1,-1,0,0,1,1,1};
int dx[] = {-1,0,1,-1,1,-1,0,1};
int find(int a){
if(a == dat[a]){
return a;
}else{
return dat[a] = find(dat[a]);
}
}
void query(int a,int b){
int aa,bb;
aa = find(a);
bb = find(b);
if(aa > bb){
swap(aa,bb);
}
dat[bb] = aa;
}
bool same(int a,int b){
if(find(a) == find(b))return true;
else return false;
};
void bfs(int sy,int sx,int idx){
queue<P>que;
int check[1005][1005];
memset(check,-1,sizeof(check));
check[sy][sx] = 0;
int cnt = maps[sy][sx] - '0';
maps[sy][sx] = '.';
dat[idx] = idx;
wake[sy][sx] = idx;
que.push((P){sy,sx});
while(!que.empty()){
int y = que.front().y;
int x = que.front().x;
que.pop();
if(check[y][x] == cnt)continue;
for(int i = 0; i < 8; ++i){
int ny = y + dy[i];
int nx = x + dx[i];
if(ny >= 0 && ny < h && nx >= 0 && nx < w && maps[ny][nx] == '#' && check[ny][nx] == -1){
maps[ny][nx] = '.';
check[ny][nx] = check[y][x] + 1;
dat[idx] = idx;
wake[ny][nx] = idx;
que.push((P){ny,nx});
}
}
}
}
void bfss(int sy,int sx){
queue<P>que;
checks[sy][sx] = 0;
que.push((P){sy,sx});
while(!que.empty()){
int y = que.front().y;
int x = que.front().x;
que.pop();
for(int i = 0; i < 8; ++i){
int ny = y + dy[i];
int nx = x + dx[i];
if(ny >= 0 && ny < h && nx >= 0 && nx < w && wake[ny][nx] != -1 && checks[ny][nx] == -1){
checks[ny][nx] = checks[y][x] + 1;
query(wake[ny][nx],wake[sy][sx]);
que.push((P){ny,nx});
}
}
}
}
int main(){
memset(dat,-1,sizeof(dat));
memset(wake,-1,sizeof(wake));
memset(checks,-1,sizeof(checks));
cin >> h >> w;
queue<P>que;
for(int i = 0; i < h; ++i){
for(int j = 0; j < w; ++j){
cin >> maps[i][j];
if('1' <= maps[i][j] && maps[i][j] <= '9'){
que.push((P){i,j});
}
}
}
int idx = 0;
while(!que.empty()){
int y = que.front().y;
int x = que.front().x;
que.pop();
bfs(y,x,idx);
idx++;
}
/*
cout << endl;
for(int i = 0; i < h; ++i){
for(int j = 0; j < w; ++j){
cout << wake[i][j];
}
cout << endl;
}
cout << endl;
*/
for(int i = 0; i < h; ++i){
for(int j = 0; j < w; ++j){
if(wake[i][j] != -1 && checks[i][j] == -1){
bfss(i,j);
}
}
}
cin >> n;
int sx,sy,gy,gx;
for(int i = 0; i < n; ++i){
cin >> sx >> sy >> gx >> gy;
if(maps[sy][sx] == '#' || maps[gy][gx] == '#'){
cout << "no" << endl;
continue;
}
if(same(wake[sy][sx],wake[gy][gx])){
cout << "yes" << endl;
}else{
cout << "no" << endl;
}
}
}

ステータス

項目 データ
問題 0004 - 韓流ハゲ
ユーザー名 IDEAL_PEAR
投稿日時 2017-08-08 11:38:20
言語 C++11
状態 Wrong Answer
得点 0
ソースコード長 3122 Byte
最大実行時間 1000 ms
最大メモリ使用量 13480 KB

セット

セット 得点 Cases
1 ALL 0 / 60 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in00.dat AC 17 ms 12640 KB
1
in01.dat AC 14 ms 12648 KB
1
in02.dat AC 19 ms 12652 KB
1
in03.dat WA 63 ms 12532 KB
1
in04.dat WA 46 ms 12792 KB
1
in05.dat WA 83 ms 12788 KB
1
in06.dat WA 192 ms 12804 KB
1
in07.dat AC 710 ms 13328 KB
1
in08.dat WA 725 ms 13320 KB
1
in09.dat TLE 1000 ms 13444 KB
1
in10.dat TLE 1000 ms 13396 KB
1
in11.dat TLE 1000 ms 13480 KB
1
in12.dat TLE 1000 ms 13428 KB
1
in13.dat TLE 1000 ms 13384 KB
1
in14.dat TLE 1000 ms 13340 KB
1
in15.dat TLE 1000 ms 13296 KB
1