Submission #00067

ソースコード

?
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
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <cstring>
#include <algorithm>
#include <vector>
//#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <map>
#include <numeric>
using namespace std;
#define elif else if
#define echo cout <<
#define read cin >>
#define fin << '\n'
#define finn cout << '\n'
#define forin(i, n) for ( int i = 0; i < n; i++ )
#define unless(flg) if(!(flg))
#define zu >>
#define und <<
#define alles(obj) obj.begin(), obj.end()
#define bash push_back
#define makePair make_pair
// type-define
#define String string
#define Stack stack
#define Queue queue
#define pQueue priority_queue
#define Vector vector
#define Pair pair
#define Map map
typedef long long llong;
typedef bool boolean;
typedef Pair<int,int> Pii;
typedef Vector<int> Vi;
// utils
const int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
boolean isMovable(int x,int y,int w,int h){return (x>=0&&y>=0&&x<w&&y<h);};
const int INF = 1 << 29;
int h, w;
char mas[1010][1010];
bool hunt[1010][1010];
int friends[1010][1010];
void bfs( int sx, int sy, int id ) {
Queue<Pii> que;
que.push( make_pair( sy, sx ) );
hunt[sy][sx] = true;
friends[sy][sx] = id;
while ( !que.empty() ) {
Pii now = que.front();
que.pop();
int y = now.first;
int x = now.second;
for ( int i = 0; i < 4; i++ ) {
int nx = x + dx[i];
int ny = y + dy[i];
if ( isMovable(nx, ny, w, h) && mas[ny][nx] != '#' && !hunt[ny][nx] ) {
hunt[ny][nx] = true;
friends[ny][nx] = id;
que.push( make_pair ( ny, nx ) );
}
}
}
}
signed main(){
cin.tie(0); ios::sync_with_stdio(false);
read h >> w;
for ( int i = 0; i < h; i++ ) {
read mas[i];
}
for ( int i = 0; i < h; i++ ) {
for ( int j = 0; j < w; j++ ) {
if ( mas[i][j] != '#' ) {
int power = mas[i][j] - '0';
for ( int k = i-power; k <= i+power; k++ ) {
for ( int l = j-power; l <= j+power; l++ ) {
if ( isMovable(l, k, w, h ) && mas[k][l] == '#' ) {
mas[k][l] = '.';
}
}
}
}
}
}
int counter = 1;
memset ( hunt, 0, sizeof( hunt ) );
for ( int i = 0; i < h; i++ ) {
for ( int j = 0; j < w; j++ ) {
if ( mas[i][j] != '#' ) {
if ( !hunt[i][j] ) {
bfs(j, i, counter++);
}
}
}
}
int n;
read n;
for ( int i = 0; i < n; i++ ) {
int sx, sy, gx, gy;
read sx >> sy >> gx >> gy;
if ( mas[sy][sx] == '#' || mas[gy][gx] == '#' ) {
echo "no" fin;
}
elif ( friends[sy][sx] == friends[gy][gx] ) {
echo "yes" fin;
}
else {
echo "no" fin;
}
}
return 0;
}

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in00.dat AC 21 ms 3552 KB
1
in01.dat AC 20 ms 3668 KB
1
in02.dat AC 25 ms 4004 KB
1
in03.dat AC 24 ms 4492 KB
1
in04.dat AC 19 ms 5380 KB
1
in05.dat AC 22 ms 5932 KB
1
in06.dat AC 30 ms 5852 KB
1
in07.dat AC 34 ms 6412 KB
1
in08.dat AC 41 ms 6408 KB
1
in09.dat AC 39 ms 6528 KB
1
in10.dat AC 42 ms 6636 KB
1
in11.dat AC 46 ms 6488 KB
1
in12.dat AC 49 ms 6604 KB
1
in13.dat AC 56 ms 6584 KB
1
in14.dat AC 45 ms 6568 KB
1
in15.dat AC 45 ms 6680 KB
1