Submission #66530

ソースコード

?
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]: 左, 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:33:55
言語 C++17
状態 Accepted
得点 5
ソースコード長 1872 Byte
最大実行時間 809 ms
最大メモリ使用量 234812 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 49 ms 4444 KB
1
in02.txt AC 181 ms 37004 KB
1
in03.txt AC 97 ms 18312 KB
1
in04.txt AC 87 ms 17012 KB
1
in05.txt AC 207 ms 44152 KB
1
in06.txt AC 603 ms 126292 KB
1
in07.txt AC 560 ms 126232 KB
1
in08.txt AC 561 ms 126140 KB
1
in09.txt AC 560 ms 126172 KB
1
in10.txt AC 562 ms 126212 KB
1
in11.txt AC 598 ms 126504 KB
1
in12.txt AC 625 ms 126568 KB
1
in13.txt AC 614 ms 126512 KB
1
in14.txt AC 611 ms 126568 KB
1
in15.txt AC 613 ms 126500 KB
1
in16.txt AC 771 ms 234764 KB
1
in17.txt AC 809 ms 234812 KB
1
in18.txt AC 218 ms 126148 KB
1
in19.txt AC 649 ms 129592 KB
1
in20.txt AC 661 ms 130180 KB
1
in21.txt AC 417 ms 126136 KB
1
in22.txt AC 426 ms 126096 KB
1
in23.txt AC 427 ms 126052 KB
1
in24.txt AC 17 ms 564 KB
1
sample01.txt AC 18 ms 648 KB
1
sample02.txt AC 20 ms 600 KB
1