#880449 (C++17) No.1638 Robot Maze

• 問題: No.1638 Robot Maze
• ユーザー: theory_and_me
• 提出日時: 2023-06-14 03:04:40
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 5 ms / 2,000 ms
• コード長: 11,509 bytes
• コンパイル時間: 2,749 ms
• コンパイル使用メモリ: 226,116 KB
• 実行使用メモリ: 6,948 KB
• 最終ジャッジ日時: 2024-06-22 15:08:03
• 合計ジャッジ時間: 3,939 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 6,816 KB
testcase_01	AC	2 ms; 6,940 KB
testcase_02	AC	1 ms; 6,940 KB
testcase_03	AC	4 ms; 6,940 KB
testcase_04	AC	2 ms; 6,940 KB
testcase_05	AC	2 ms; 6,940 KB
testcase_06	AC	2 ms; 6,944 KB
testcase_07	AC	2 ms; 6,940 KB
testcase_08	AC	1 ms; 6,940 KB
testcase_09	AC	2 ms; 6,940 KB
testcase_10	AC	1 ms; 6,940 KB
testcase_11	AC	1 ms; 6,940 KB
testcase_12	AC	2 ms; 6,940 KB
testcase_13	AC	2 ms; 6,944 KB
testcase_14	AC	5 ms; 6,944 KB
testcase_15	AC	3 ms; 6,944 KB
testcase_16	AC	4 ms; 6,940 KB
testcase_17	AC	3 ms; 6,944 KB
testcase_18	AC	4 ms; 6,940 KB
testcase_19	AC	4 ms; 6,940 KB
testcase_20	AC	4 ms; 6,944 KB
testcase_21	AC	3 ms; 6,940 KB
testcase_22	AC	3 ms; 6,944 KB
testcase_23	AC	4 ms; 6,940 KB
testcase_24	AC	3 ms; 6,940 KB
testcase_25	AC	4 ms; 6,944 KB
testcase_26	AC	3 ms; 6,940 KB
testcase_27	AC	4 ms; 6,940 KB
testcase_28	AC	3 ms; 6,944 KB
testcase_29	AC	3 ms; 6,944 KB
testcase_30	AC	2 ms; 6,940 KB
testcase_31	AC	2 ms; 6,944 KB
testcase_32	AC	4 ms; 6,944 KB
testcase_33	AC	4 ms; 6,940 KB
testcase_34	AC	5 ms; 6,944 KB
testcase_35	AC	4 ms; 6,940 KB
testcase_36	AC	5 ms; 6,940 KB
testcase_37	AC	4 ms; 6,940 KB
testcase_38	AC	4 ms; 6,944 KB
testcase_39	AC	5 ms; 6,940 KB
testcase_40	AC	5 ms; 6,940 KB
testcase_41	AC	5 ms; 6,944 KB
testcase_42	AC	5 ms; 6,944 KB
testcase_43	AC	5 ms; 6,944 KB
testcase_44	AC	5 ms; 6,940 KB
testcase_45	AC	4 ms; 6,944 KB
testcase_46	AC	5 ms; 6,944 KB
testcase_47	AC	4 ms; 6,940 KB
testcase_48	AC	4 ms; 6,940 KB
testcase_49	AC	4 ms; 6,944 KB
testcase_50	AC	5 ms; 6,948 KB
testcase_51	AC	4 ms; 6,940 KB

ソースコード

#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.hpp
template <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;
}