Submission #00117

ソースコード

?
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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int,int> pii;
int dx[]={0,1,0,-1};
int dy[]={-1,0,1,0};
char mp[1005][1005];
int dist[1005][1005];
int sy,sx,gy,gx;
int h,w;
int cnt=0;
int cnt_i[1000001];
int cnt_j[1000001];
int a[1000001];
int dfs(int sx,int sy);
int main(){
int n,ff=0;
cin >> h >> w;
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
cin >> mp[i][j];
}
}
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
if(mp[i][j]!='#'&&mp[i][j]!='.'){
a[cnt]=(int)mp[i][j]-'0';
cnt_i[cnt]=i;
cnt_j[cnt]=j;
cnt++;
mp[i][j]='.';
}
}
}
for(int c=0;c<cnt;c++){
for(int k=cnt_i[c]-a[c];k<=cnt_i[c]+a[c];k++){
for(int l=cnt_j[c]-a[c];l<=cnt_j[c]+a[c];l++){
if(0<=k&&0<=l&&h>k&&w>l&&mp[k][l]=='#'){
mp[k][l]='.';
}
}
}
}
cin >> n;
for(int i=0;i<n;i++){
cin >> sx >> sy >> gx >> gy;
ff=dfs(sx,sy);
if(ff==1){
cout << "yes" << endl;
}else{
cout << "no" << endl;
}
}
}
int dfs(int sx,int sy){
int f=0;
memset(dist,-1,sizeof(dist));
queue<pii> que;
que.push(make_pair(sy,sx));
if(mp[sy][sx]=='#'||mp[gy][gx]=='#'){
return f;
}else{
while(!que.empty()){
pii now=que.front();
que.pop();
int y = now.first;
int x = now.second;
if(x==gx&&y==gy){
f=1;
break;
}
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(0<=nx&&0<=ny&&nx<w&&ny<h&&mp[ny][nx]!='#'&&dist[ny][nx]==-1){
dist[ny][nx]=1;
que.push(make_pair(ny,nx));
}
}
}
return f;
}
}

ステータス

項目 データ
問題 0002 - 韓流ハゲ
ユーザー名 ei1825
投稿日時 2018-08-22 12:37:04
言語 C++11
状態 Time Limit Exceeded
得点 0
ソースコード長 1705 Byte
最大実行時間 1000 ms
最大メモリ使用量 11164 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in00.dat AC 24 ms 10720 KB
1
in01.dat AC 29 ms 10692 KB
1
in02.dat AC 23 ms 10668 KB
1
in03.dat AC 49 ms 10764 KB
1
in04.dat AC 26 ms 10732 KB
1
in05.dat AC 31 ms 10700 KB
1
in06.dat AC 88 ms 10800 KB
1
in07.dat AC 67 ms 11020 KB
1
in08.dat AC 163 ms 11080 KB
1
in09.dat TLE 1000 ms 11008 KB
1
in10.dat TLE 1000 ms 11164 KB
1
in11.dat TLE 1000 ms 11060 KB
1
in12.dat TLE 1000 ms 11088 KB
1
in13.dat TLE 1000 ms 10984 KB
1
in14.dat TLE 1000 ms 11016 KB
1
in15.dat TLE 1000 ms 11048 KB
1