Submission #66533

ソースコード

?
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
#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){
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]: 左, dist*[3]: 上, dist*[4]: {右上,右下,左上,左下}
vector dist(h, vector(w, vector(5, INF)));
deque<tuple<int, int, int> > que;
dist[sy][sx][4] = 0;
que.emplace_back(sy, sx, 4);
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 = min(i, 4);
if(!inside(ny, nx) || s[ny][nx] == '#') continue;
if(nd != 4 && 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 < 5; ++i){
chmin(ans, dist[gy][gx][i]);
}
if(ans == INF){
cout << -1 << '\n';
}else{
cout << ans << '\n';
}
return 0;
}

ステータス

項目 データ
問題 1498 - 竜王
ユーザー名 ei1903
投稿日時 2021-05-06 23:35:19
言語 C++17
状態 Accepted
得点 5
ソースコード長 1810 Byte
最大実行時間 832 ms
最大メモリ使用量 235284 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 41 ms 4444 KB
1
in02.txt AC 189 ms 37228 KB
1
in03.txt AC 103 ms 18408 KB
1
in04.txt AC 94 ms 17232 KB
1
in05.txt AC 224 ms 44456 KB
1
in06.txt AC 602 ms 126752 KB
1
in07.txt AC 600 ms 126716 KB
1
in08.txt AC 597 ms 126784 KB
1
in09.txt AC 606 ms 126844 KB
1
in10.txt AC 617 ms 126772 KB
1
in11.txt AC 646 ms 127092 KB
1
in12.txt AC 635 ms 127052 KB
1
in13.txt AC 639 ms 127020 KB
1
in14.txt AC 664 ms 127096 KB
1
in15.txt AC 650 ms 127048 KB
1
in16.txt AC 813 ms 235204 KB
1
in17.txt AC 832 ms 235284 KB
1
in18.txt AC 264 ms 126652 KB
1
in19.txt AC 693 ms 130112 KB
1
in20.txt AC 689 ms 130728 KB
1
in21.txt AC 460 ms 126716 KB
1
in22.txt AC 453 ms 126572 KB
1
in23.txt AC 474 ms 126552 KB
1
in24.txt AC 20 ms 576 KB
1
sample01.txt AC 21 ms 544 KB
1
sample02.txt AC 23 ms 640 KB
1