結果
問題 | No.1638 Robot Maze |
ユーザー |
![]() |
提出日時 | 2021-08-06 21:29:01 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 6 ms / 2,000 ms |
コード長 | 1,772 bytes |
コンパイル時間 | 1,861 ms |
コンパイル使用メモリ | 184,340 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-17 01:20:59 |
合計ジャッジ時間 | 2,969 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main(){ int H, W; cin >> H >> W; int U, D, R, L; long long K; int P; cin >> U >> D >> R >> L >> K >> P; int xs, ys, xt, yt; cin >> xs >> ys >> xt >> yt; xs--; ys--; xt--; yt--; vector<vector<char>> C(H, vector<char>(W)); for (int i = 0; i < H; i++){ for (int j = 0; j < W; j++){ cin >> C[i][j]; } } vector<vector<long long>> d(H, vector<long long>(W, -1)); priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<tuple<long long, int, int>>> pq; pq.push(make_tuple(0, xs, ys)); while (!pq.empty()){ long long dd = get<0>(pq.top()); int x = get<1>(pq.top()); int y = get<2>(pq.top()); pq.pop(); if (d[x][y] == -1){ d[x][y] = dd; if (x > 0){ if (C[x - 1][y] == '.'){ pq.push(make_tuple(dd + U, x - 1, y)); } if (C[x - 1][y] == '@'){ pq.push(make_tuple(dd + U + P, x - 1, y)); } } if (x < H - 1){ if (C[x + 1][y] == '.'){ pq.push(make_tuple(dd + D, x + 1, y)); } if (C[x + 1][y] == '@'){ pq.push(make_tuple(dd + D + P, x + 1, y)); } } if (y < W - 1){ if (C[x][y + 1] == '.'){ pq.push(make_tuple(dd + R, x, y + 1)); } if (C[x][y + 1] == '@'){ pq.push(make_tuple(dd + R + P, x, y + 1)); } } if (y > 0){ if (C[x][y - 1] == '.'){ pq.push(make_tuple(dd + L, x, y - 1)); } if (C[x][y - 1] == '@'){ pq.push(make_tuple(dd + L + P, x, y - 1)); } } } } if (d[xt][yt] != -1 && d[xt][yt] <= K){ cout << "Yes" << endl; } else { cout << "No" << endl; } }