Submission #00030

ソースコード

?
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
#include<bits/stdc++.h>
#define INF 100000000
using namespace std;
typedef struct{
int x,y;
int num;
}BOMB;
typedef struct{
int x,y;
}Point;
int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};
int d[1001][1001];
char maps[1001][1001];
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int h,w,n;
vector<BOMB>bomb;
queue<Point>que;
cin >> h >> w;
for(int i = 0;i < h;i++){
for(int j = 0;j < w;j++){
cin >> maps[i][j];
d[i][j] = INF;
if(maps[i][j] != '#'){
bomb.push_back((BOMB){j,i,maps[i][j] - '0'});
}
}
}
for(int k = 0;k < bomb.size();k++){
BOMB temp = bomb[k];
int num = temp.num;
int x = temp.x - num;
int y = temp.y - num;
for(int i = 0;i < num * 2 + 1;i++){
for(int j = 0;j < num * 2 + 1;j++){
int nx = x + j;
int ny = y + i;
if(nx >= 0 && nx < w && ny >= 0 && ny < h){
maps[ny][nx] = '.';
}
}
}
}
int key = 1;
for(int i = 0;i < h;i++){
for(int j = 0;j < w;j++){
if(maps[i][j] == '.' && d[i][j] == INF){
que.push((Point){j,i});
d[i][j] = key;
while(!que.empty()){
Point p = que.front(); que.pop();
int x = p.x;
int y = p.y;
for(int l = 0;l < 4;l++){
int nx = dx[l] + x;
int ny = dy[l] + y;
if(nx >= 0 && nx < w && ny >= 0 && ny < h && maps[ny][nx] == '.' && d[ny][nx] == INF){
que.push((Point){nx,ny});
d[ny][nx] = key;
}
}
}
key ++;
}
}
}
cin >> n;
for(int i = 0;i < n;i++){
int sx,sy,gx,gy;
cin >> sx >> sy >> gx >> gy;
if(d[sy][sx] == d[gy][gx] && d[sy][sx] != INF && d[gy][gx] != INF){
cout << "yes" << endl;
}else{
cout << "no" << endl;
}
}
return 0;
}

ステータス

項目 データ
問題 0002 - 韓流ハゲ
ユーザー名 HTNei1730
投稿日時 2018-08-22 10:38:01
言語 C++11
状態 Accepted
得点 10
ソースコード長 1804 Byte
最大実行時間 66 ms
最大メモリ使用量 5840 KB

セット

セット 得点 Cases
1 ALL 10 / 10 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in00.dat AC 19 ms 608 KB
1
in01.dat AC 16 ms 856 KB
1
in02.dat AC 18 ms 976 KB
1
in03.dat AC 26 ms 1468 KB
1
in04.dat AC 18 ms 4016 KB
1
in05.dat AC 22 ms 4168 KB
1
in06.dat AC 31 ms 4208 KB
1
in07.dat AC 46 ms 5632 KB
1
in08.dat AC 44 ms 5644 KB
1
in09.dat AC 47 ms 5600 KB
1
in10.dat AC 48 ms 5596 KB
1
in11.dat AC 59 ms 5716 KB
1
in12.dat AC 53 ms 5840 KB
1
in13.dat AC 57 ms 5832 KB
1
in14.dat AC 66 ms 5700 KB
1
in15.dat AC 66 ms 5688 KB
1