Submission #66765

ソースコード

?
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 % 2 : 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:40:07
言語 C++17
状態 Accepted
得点 5
ソースコード長 1872 Byte
最大実行時間 638 ms
最大メモリ使用量 180432 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 45 ms 4444 KB
1
in02.txt AC 178 ms 36764 KB
1
in03.txt AC 97 ms 18108 KB
1
in04.txt AC 86 ms 16948 KB
1
in05.txt AC 198 ms 43980 KB
1
in06.txt AC 520 ms 126300 KB
1
in07.txt AC 539 ms 126308 KB
1
in08.txt AC 522 ms 126288 KB
1
in09.txt AC 521 ms 126260 KB
1
in10.txt AC 529 ms 126240 KB
1
in11.txt AC 536 ms 126468 KB
1
in12.txt AC 542 ms 126428 KB
1
in13.txt AC 557 ms 126520 KB
1
in14.txt AC 541 ms 126332 KB
1
in15.txt AC 555 ms 126536 KB
1
in16.txt AC 625 ms 180392 KB
1
in17.txt AC 638 ms 180432 KB
1
in18.txt AC 218 ms 126072 KB
1
in19.txt AC 500 ms 128100 KB
1
in20.txt AC 507 ms 128388 KB
1
in21.txt AC 418 ms 126124 KB
1
in22.txt AC 425 ms 126212 KB
1
in23.txt AC 431 ms 126048 KB
1
in24.txt AC 19 ms 692 KB
1
sample01.txt AC 31 ms 636 KB
1
sample02.txt AC 21 ms 580 KB
1