Submission #64785

ソースコード

?
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
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
const char newl = '\n';
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}
template<typename T=int>
vector<T> read(size_t n){
vector<T> ts(n);
for(size_t i=0;i<n;i++) cin>>ts[i];
return ts;
}
//INSERT ABOVE HERE
const int MAX = 1010;
const int INF = 1e9;
int dist[2][MAX][MAX];
int color[2][MAX][MAX];
signed main(){
cin.tie(0);
ios::sync_with_stdio(0);
int n,m;
cin>>n>>m;
auto st=read<string>(n);
struct State{
int z,y,x,d,c;
};
queue<State> que;
auto push=[&](State cur){
if(dist[cur.z][cur.y][cur.x]<=cur.d) return;
if(cur.z>0 and color[0][cur.y][cur.x]==cur.c) return;
dist[cur.z][cur.y][cur.x]=cur.d;
color[cur.z][cur.y][cur.x]=cur.c;
que.emplace(cur);
};
using P = pair<int, int>;
map<P, int> idx;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
dist[0][i][j]=dist[1][i][j]=INF;
color[0][i][j]=color[1][i][j]=-1;
if(st[i][j]!='E') continue;
color[0][i][j]=idx.size();
State cur({0,i,j,0,color[0][i][j]});
idx[P(i,j)]=cur.c;
push(cur);
}
}
while(!que.empty()){
State cur=que.front();que.pop();
if(dist[cur.z][cur.y][cur.x]<cur.d) continue;
// cout<<cur.z<<' '<<cur.y<<' '<<cur.x<<' '<<cur.d<<' '<<cur.c<<endl;
int dy[4]={0,0,1,-1};
int dx[4]={1,-1,0,0};
auto in=[&](int y,int x){return 0<=y and y<n and 0<=x and x<m;};
for(int k=0;k<4;k++){
int ny=cur.y+dy[k],nx=cur.x+dx[k];
if(!in(ny,nx) or st[ny][nx]=='#') continue;
push(State({0,ny,nx,cur.d+1,cur.c}));
push(State({1,ny,nx,cur.d+1,cur.c}));
}
}
int q;
cin>>q;
for(int i=0;i<q;i++){
int sr,sc,br,bc;
cin>>sr>>sc>>br>>bc;
cout<<dist[color[0][sr][sc]==idx[P(br,bc)]][sr][sc]<<newl;
}
return 0;
}

ステータス

項目 データ
問題 1457 - 壊れた出口
ユーザー名 syoribu
投稿日時 2020-11-20 12:26:29
言語 C++17
状態 Accepted
得点 9
ソースコード長 2072 Byte
最大実行時間 245 ms
最大メモリ使用量 70364 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1 AC 23 ms 6748 KB
1
in2 AC 31 ms 8496 KB
1
in3 AC 16 ms 10412 KB
1
in4 AC 20 ms 10488 KB
1
in5 AC 18 ms 10440 KB
1
in6 AC 31 ms 10500 KB
1
in7 AC 17 ms 10552 KB
1
in8 AC 27 ms 10608 KB
1
in9 AC 25 ms 10616 KB
1
in10 AC 17 ms 13220 KB
1
in11 AC 28 ms 13960 KB
1
in12 AC 34 ms 14728 KB
1
in13 AC 117 ms 20508 KB
1
in14 AC 148 ms 21276 KB
1
in15 AC 132 ms 31768 KB
1
in16 AC 159 ms 35648 KB
1
in17 AC 109 ms 19152 KB
1
in18 AC 234 ms 70364 KB
1
in19 AC 104 ms 19412 KB
1
in20 AC 78 ms 20092 KB
1
in21 AC 111 ms 20612 KB
1
in22 AC 233 ms 62332 KB
1
in23 AC 245 ms 62696 KB
1
in24 AC 214 ms 62800 KB
1