Submission #66766

ソースコード

?
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
#include <iostream>
#include <vector>
#include <deque>
#include <tuple>
#include <climits>
using namespace std;
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
const int dx[] = {1,0,-1,0,1,1,-1,-1};
const int dy[] = {0,-1,0,1,1,-1,-1,1};
const int INF = INT_MAX / 2;
signed main(void){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int h, w;
int sy, sx, gy, gx;
cin >> h >> w >> sy >> sx >> gy >> gx;
--sy, --sx, --gy, --gx;
vector<string> s(h);
for(int i = 0; i < h; ++i){
cin >> s[i];
}
auto inside = [&](int y, int x){
return (0 <= y && y < h && 0 <= x && x < w);
};
// dist*[0]: 左右, dist*[1]: 上下, dist*[2]: {右上,右下,左上,左下}
vector dist(h, vector(w, vector(3, INF)));
deque<tuple<int, int, int> > que;
dist[sy][sx][2] = 0;
que.emplace_back(sy, sx, 2);
while(!que.empty()){
auto [cy, cx, cd] = que.front();
que.pop_front();
for(int i = 0; i < 8; ++i){
int ny = cy + dy[i];
int nx = cx + dx[i];
int nd = (i < 4 ? i & 1 : 2);
if(!inside(ny, nx) || s[ny][nx] == '#') continue;
if(nd != 2 && nd == cd){
if(chmin(dist[ny][nx][nd], dist[cy][cx][cd])){
que.emplace_front(ny, nx, nd);
}
}else{
if(chmin(dist[ny][nx][nd], dist[cy][cx][cd] + 1)){
que.emplace_back(ny, nx, nd);
}
}
}
}
int ans = INF;
for(int i = 0; i < 3; ++i){
chmin(ans, dist[gy][gx][i]);
}
if(ans == INF){
cout << -1 << '\n';
}else{
cout << ans << '\n';
}
return 0;
}

ステータス

項目 データ
問題 1498 - 竜王
ユーザー名 ei1903
投稿日時 2021-05-18 22:41:27
言語 C++17
状態 Accepted
得点 5
ソースコード長 1872 Byte
最大実行時間 642 ms
最大メモリ使用量 180572 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 36 ms 4444 KB
1
in02.txt AC 175 ms 36760 KB
1
in03.txt AC 98 ms 18104 KB
1
in04.txt AC 88 ms 16820 KB
1
in05.txt AC 205 ms 43860 KB
1
in06.txt AC 528 ms 126056 KB
1
in07.txt AC 524 ms 126056 KB
1
in08.txt AC 548 ms 126164 KB
1
in09.txt AC 524 ms 126140 KB
1
in10.txt AC 531 ms 126124 KB
1
in11.txt AC 559 ms 126360 KB
1
in12.txt AC 581 ms 126312 KB
1
in13.txt AC 527 ms 126408 KB
1
in14.txt AC 539 ms 126344 KB
1
in15.txt AC 550 ms 126420 KB
1
in16.txt AC 615 ms 180532 KB
1
in17.txt AC 642 ms 180572 KB
1
in18.txt AC 221 ms 126204 KB
1
in19.txt AC 510 ms 128236 KB
1
in20.txt AC 511 ms 128656 KB
1
in21.txt AC 418 ms 126132 KB
1
in22.txt AC 436 ms 126092 KB
1
in23.txt AC 438 ms 126052 KB
1
in24.txt AC 23 ms 568 KB
1
sample01.txt AC 20 ms 776 KB
1
sample02.txt AC 18 ms 604 KB
1