結果
問題 | No.1572 XI |
ユーザー | chocorusk |
提出日時 | 2021-08-15 03:18:37 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 326 ms / 2,000 ms |
コード長 | 1,815 bytes |
コンパイル時間 | 3,848 ms |
コンパイル使用メモリ | 192,068 KB |
実行使用メモリ | 29,312 KB |
最終ジャッジ日時 | 2024-04-16 01:31:56 |
合計ジャッジ時間 | 12,013 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 3 ms
5,376 KB |
testcase_04 | AC | 64 ms
11,264 KB |
testcase_05 | AC | 153 ms
16,512 KB |
testcase_06 | AC | 184 ms
24,448 KB |
testcase_07 | AC | 5 ms
5,376 KB |
testcase_08 | AC | 157 ms
21,504 KB |
testcase_09 | AC | 82 ms
27,264 KB |
testcase_10 | AC | 126 ms
25,984 KB |
testcase_11 | AC | 11 ms
5,376 KB |
testcase_12 | AC | 62 ms
23,552 KB |
testcase_13 | AC | 17 ms
11,136 KB |
testcase_14 | AC | 58 ms
17,536 KB |
testcase_15 | AC | 12 ms
5,376 KB |
testcase_16 | AC | 51 ms
20,352 KB |
testcase_17 | AC | 12 ms
12,800 KB |
testcase_18 | AC | 73 ms
24,064 KB |
testcase_19 | AC | 163 ms
23,936 KB |
testcase_20 | AC | 110 ms
24,960 KB |
testcase_21 | AC | 197 ms
22,400 KB |
testcase_22 | AC | 151 ms
21,632 KB |
testcase_23 | AC | 8 ms
8,448 KB |
testcase_24 | AC | 2 ms
5,376 KB |
testcase_25 | AC | 2 ms
5,376 KB |
testcase_26 | AC | 2 ms
5,376 KB |
testcase_27 | AC | 2 ms
5,376 KB |
testcase_28 | AC | 2 ms
5,376 KB |
testcase_29 | AC | 2 ms
5,376 KB |
testcase_30 | AC | 2 ms
5,376 KB |
testcase_31 | AC | 2 ms
5,376 KB |
testcase_32 | AC | 2 ms
5,376 KB |
testcase_33 | AC | 2 ms
5,376 KB |
testcase_34 | AC | 297 ms
27,264 KB |
testcase_35 | AC | 287 ms
28,032 KB |
testcase_36 | AC | 290 ms
27,648 KB |
testcase_37 | AC | 308 ms
28,160 KB |
testcase_38 | AC | 291 ms
28,160 KB |
testcase_39 | AC | 309 ms
28,544 KB |
testcase_40 | AC | 286 ms
26,368 KB |
testcase_41 | AC | 301 ms
27,520 KB |
testcase_42 | AC | 297 ms
28,288 KB |
testcase_43 | AC | 292 ms
28,160 KB |
testcase_44 | AC | 318 ms
29,312 KB |
testcase_45 | AC | 326 ms
29,312 KB |
testcase_46 | AC | 316 ms
29,312 KB |
testcase_47 | AC | 41 ms
29,184 KB |
testcase_48 | AC | 305 ms
29,184 KB |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #include <list> #include <atcoder/all> #define popcount __builtin_popcount using namespace std; using namespace atcoder; typedef long long ll; typedef pair<int, int> P; using mint=modint998244353; int h, w; int sy, sx, gy, gx; string s[1010]; int d[6][1010][1010]; int main() { cin>>h>>w; cin>>sy>>sx; cin>>gy>>gx; sy--; sx--; gy--; gx--; for(int i=0; i<h; i++){ cin>>s[i]; } const int INF=1e9; for(int i=0; i<h; i++){ for(int j=0; j<w; j++){ for(int k=0; k<6; k++){ d[k][i][j]=INF; } } } d[0][sy][sx]=0; using Pi=pair<P, int>; queue<Pi> que; que.push({{sy, sx}, 0}); int dy[4]={1, -1, 0, 0}, dx[4]={0, 0, 1, -1}; vector<vector<int>> v{{2,3,4,5},{3,2,5,4},{1,0,2,2},{0,1,3,3},{4,4,1,0},{5,5,0,1}}; while(!que.empty()){ auto p=que.front(); que.pop(); int t=p.second; int y=p.first.first, x=p.first.second; for(int k=0; k<4; k++){ int y1=y+dy[k], x1=x+dx[k]; if(y1<0 || y1>=h || x1<0 || x1>=w || s[y1][x1]=='#') continue; int t1=v[t][k]; if(d[t1][y1][x1]>d[t][y][x]+1){ d[t1][y1][x1]=d[t][y][x]+1; que.push({{y1, x1}, t1}); } } } if(d[0][gy][gx]==INF) cout<<-1<<endl; else cout<<d[0][gy][gx]<<endl; return 0; }