結果
| 問題 | No.1638 Robot Maze |
| ユーザー |
 theory_and_me
|
| 提出日時 | 2023-06-14 03:04:40 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 7 ms / 2,000 ms |
| コード長 | 11,509 bytes |
| コンパイル時間 | 2,538 ms |
| コンパイル使用メモリ | 217,740 KB |
| 最終ジャッジ日時 | 2025-02-14 02:31:29 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 49 |
ソースコード
#line 1 "grid_Dijkstra.test.cpp"#define PROBLEM "https://yukicoder.me/problems/no/1638"#line 2 "/Users/akagiyasunori/Work/procon/lib/heuristic_lib/data_structures/radix_heap.hpp"#include <array>#include <cstddef>#include <limits>#include <tuple>#include <type_traits>#include <utility>#include <vector>// Radix heap for unsigned integer// https://github.com/iwiwi/radix-heap// hitonanode さんの radix heap. https://hitonanode.github.io/cplib-cpp/data_structure/radix_heap.hpptemplate <class Uint, class Label, typename std::enable_if<std::is_unsigned<Uint>::value>::type * = nullptr>class radix_heap {int sz;Uint last;std::array<std::vector<std::pair<Uint, Label>>, std::numeric_limits<Uint>::digits + 1> v;template <class U, typename std::enable_if<sizeof(U) == 4>::type * = nullptr>static inline int bucket(U x) noexcept {return x ? 32 - __builtin_clz(x) : 0;}template <class U, typename std::enable_if<sizeof(U) == 8>::type * = nullptr>static inline int bucket(U x) noexcept {return x ? 64 - __builtin_clzll(x) : 0;}void pull() {if (!v[0].empty()) return;int i = 1;while (v[i].empty()) ++i;last = v[i].back().first;for (int j = 0; j < int(v[i].size()); j++) last = std::min(last, v[i][j].first);for (int j = 0; j < int(v[i].size()); j++) {v[bucket(v[i][j].first ^ last)].emplace_back(std::move(v[i][j]));}v[i].clear();}public:radix_heap() : sz(0), last(0) {static_assert(std::numeric_limits<Uint>::digits > 0, "Invalid type.");}std::size_t size() const noexcept { return sz; }bool empty() const noexcept { return sz == 0; }void push(Uint x, const Label &val) { ++sz, v[bucket(x ^ last)].emplace_back(x, val); }void push(Uint x, Label &&val) { ++sz, v[bucket(x ^ last)].emplace_back(x, std::move(val)); }template <class... Args> void emplace(Uint x, Args &&...args) {++sz, v[bucket(x ^ last)].emplace_back(std::piecewise_construct, std::forward_as_tuple(x),std::forward_as_tuple(args...));}void pop() { pull(), --sz, v[0].pop_back(); }std::pair<Uint, Label> top() { return pull(), v[0].back(); }Uint top_key() { return pull(), last; }Label &top_label() { return pull(), v[0].back().second; }void clear() noexcept {sz = 0, last = 0;for (auto &vec : v) vec.clear();}void swap(radix_heap<Uint, Label> &a) {std::swap(sz, a.sz), std::swap(last, a.last), v.swap(a.v);}};#line 2 "/Users/akagiyasunori/Work/procon/lib/heuristic_lib/grid/grid_template.hpp"#include <bits/stdc++.h>using namespace std;using ll = long long;template<typename T> // T は辺のコストの型struct grid_template{const T T_INF = numeric_limits<T>::max();const int num_dirs = 4;const vector<int> dx = {0, -1, 0, 1};const vector<int> dy = {-1, 0, 1, 0};const vector<char> dc = {'L', 'U', 'R', 'D'};// H: 縦の長さ W: 横の長さ// access: 移動コストを表現する3次元配列．access[x][y][dir] はマス(x, y)から方向dirに進むときのコストを表す．-1の場合は移動不可能．int H, W;vector<vector<vector<T>>> access;vector<T> access_array;bool array_flag = false;grid_template(int H, int W): H(H), W(W){access.resize(H);for(int i=0;i<H;i++) access[i].resize(W);for(int i=0;i<H;i++) for(int j=0;j<W;j++) access[i][j].resize(num_dirs);for(int i=0;i<H;i++) for(int j=0;j<W;j++) for(int k=0;k<num_dirs;k++) access[i][j][k] = -1;access_array.resize(H * W * num_dirs);}int encode_access(int x, int y, int z){return x * W * num_dirs + y * num_dirs + z;}int encode_grid(int x, int y){return x * W + y;}pair<int, int> decode_grid(int x){return {x / W, x % W};}void make_access_array(){for(int i=0;i<H;i++){for(int j=0;j<W;j++){for(int k=0;k<num_dirs;k++){access_array[encode_access(i, j, k)] = access[i][j][k];}}}array_flag = true;}// BFS·. 辺重みが1のみの場合しか使えないvector<vector<T>> bfs(int sx, int sy){if(!array_flag) make_access_array();vector<T> dist(H * W, -1);queue<int> qu;int s = encode_grid(sx, sy);dist[s] = 0;qu.emplace(s);while(!qu.empty()){auto v_cur = qu.front();qu.pop();auto [cx, cy] = decode_grid(v_cur);for(int i=0;i<num_dirs;i++){int nx = cx + dx[i];int ny = cy + dy[i];int v_next = encode_grid(nx, ny);if(access_array[encode_access(cx, cy, i)] == -1) continue;if(dist[v_next] != -1) continue;dist[encode_grid(nx, ny)] = dist[v_cur] + access_array[encode_access(cx, cy, i)];qu.emplace(v_next);}}vector<vector<T>> dist_grid(H, vector<T>(W));for(int i=0;i<H;i++){for(int j=0;j<W;j++){dist_grid[i][j] = dist[encode_grid(i, j)];}}return dist_grid;}// 経路復元付きBFS·. 辺重みが1のみの場合しか使えないtuple<T, string> bfs_reconstruction(int sx, int sy, int tx, int ty){if(!array_flag) make_access_array();vector<T> dist(H * W, -1);vector<T> pre_v(H * W, -1);queue<int> qu;int s = encode_grid(sx, sy);dist[s] = 0;qu.emplace(s);while(!qu.empty()){auto v_cur = qu.front();qu.pop();auto [cx, cy] = decode_grid(v_cur);for(int i=0;i<num_dirs;i++){int nx = cx + dx[i];int ny = cy + dy[i];int v_next = encode_grid(nx, ny);if(access_array[encode_access(cx, cy, i)] == -1) continue;if(dist[v_next] != -1) continue;dist[encode_grid(nx, ny)] = dist[v_cur] + access_array[encode_access(cx, cy, i)];pre_v[v_next] = v_cur;qu.emplace(v_next);}}string route = "";if(dist[encode_grid(tx, ty)] == -1){return {-1, route};}int v_cur = encode_grid(tx, ty);while(v_cur != s){int v_pre = pre_v[v_cur];auto [cx, cy] = decode_grid(v_cur);auto [px, py] = decode_grid(v_pre);for(int i=0;i<4;i++){if(dx[i] == cx - px and dy[i] == cy - py){route.push_back(dc[i]);}}v_cur = v_pre;}reverse(route.begin(), route.end());return {dist[encode_grid(tx, ty)], route};}// Dijkstra法による最短経路．負辺は扱えないvector<vector<T>> Dijkstra(int sx, int sy){if(!array_flag) make_access_array();int s = encode_grid(sx, sy);vector<T> dist(H * W, T_INF);vector<int> pre_v(H * W, T_INF);using Pi = pair<T, int>;priority_queue<Pi, vector<Pi>, greater<Pi>> pq;// radix_heap<typename std::make_unsigned<T>::type, int> pq; // 符号なし整数にしか使えないが，定数倍が高速dist[s] = 0;pq.emplace(0, s);while(!pq.empty()){auto [cost, v_cur] = pq.top();pq.pop();auto [x_cur, y_cur] = decode_grid(v_cur);if(dist[v_cur] < cost) continue;for(int i=0;i<num_dirs;i++){if(access_array[v_cur * num_dirs + i] == -1) continue;auto cost_next = cost + access_array[v_cur * num_dirs + i];int x_next = x_cur + dx[i];int y_next = y_cur + dy[i];int v_next = encode_grid(x_next, y_next);if(dist[v_next] <= cost_next) continue;dist[v_next] = cost_next;pq.emplace(dist[v_next], v_next);}}vector<vector<T>> dist_grid(H, vector<T>(W));for(int i=0;i<H;i++){for(int j=0;j<W;j++){dist_grid[i][j] = dist[encode_grid(i, j)];}}return dist_grid;}// Dijkstra法による経路復元付き最短経路．負辺は扱えないtuple<T, string> Dijkstra_reconstruction(int sx, int sy, int tx, int ty){if(!array_flag) make_access_array();int s = encode_grid(sx, sy);vector<T> dist(H * W, T_INF);vector<int> pre_v(H * W, T_INF);using Pi = pair<T, int>;priority_queue<Pi, vector<Pi>, greater<Pi>> pq;// radix_heap<typename std::make_unsigned<T>::type, int> pq; // 符号なし整数にしか使えないが，定数倍が高速dist[s] = 0;pq.emplace(0, s);while(!pq.empty()){auto [cost, v_cur] = pq.top();pq.pop();auto [x_cur, y_cur] = decode_grid(v_cur);if(dist[v_cur] < cost) continue;for(int i=0;i<num_dirs;i++){if(access_array[v_cur * num_dirs + i] == -1) continue;auto cost_next = cost + access_array[v_cur * num_dirs + i];int x_next = x_cur + dx[i];int y_next = y_cur + dy[i];int v_next = encode_grid(x_next, y_next);if(dist[v_next] <= cost_next) continue;dist[v_next] = cost_next;pre_v[v_next] = v_cur;pq.emplace(dist[v_next], v_next);}}string route = "";if(dist[encode_grid(tx, ty)] == T_INF){return {dist[encode_grid(tx, ty)], route};}int v_cur = encode_grid(tx, ty);while(v_cur != s){int v_pre = pre_v[v_cur];auto [cx, cy] = decode_grid(v_cur);auto [px, py] = decode_grid(v_pre);for(int i=0;i<4;i++){if(dx[i] == cx - px and dy[i] == cy - py){route.push_back(dc[i]);break;}}v_cur = v_pre;}reverse(route.begin(), route.end());return {dist[encode_grid(tx, ty)], route};}};#line 3 "grid_Dijkstra.test.cpp"#line 5 "grid_Dijkstra.test.cpp"using namespace std;using ll = long long;int main(){int H, W;cin >> H >> W;vector<ll> C(4);cin >> C[1] >> C[3] >> C[2] >> C[0];ll K, P;cin >> K >> P;int sx, sy, tx, ty;cin >> sx >> sy >> tx >> ty;sx--, sy--, tx--, ty--;vector<string> S(H);for(int i=0;i<H;i++){cin >> S[i];}grid_template<ll> G(H, W);for(int i=0;i<H;i++){for(int j=0;j<W;j++){for(int k=0;k<(int)G.num_dirs;k++){int nx = i + G.dx[k];int ny = j + G.dy[k];if(nx >= 0 and nx < H and ny >= 0 and ny < W and S[nx][ny] != '#'){G.access[i][j][k] = C[k];if(S[nx][ny] == '@') G.access[i][j][k] += P;}}}}auto dist = G.Dijkstra(sx, sy);// cout << dist[tx][ty] << endl;cout << (dist[tx][ty] <= K ? "Yes" : "No") << endl;}