結果

問題 No.2411 Reverse Directions
ユーザー hari64hari64
提出日時 2023-07-19 20:00:28
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 8,503 bytes
コンパイル時間 4,678 ms
コンパイル使用メモリ 224,384 KB
実行使用メモリ 8,192 KB
最終ジャッジ日時 2024-04-18 00:58:01
合計ジャッジ時間 10,130 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 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 RE -
testcase_05 AC 2 ms
5,376 KB
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 AC 18 ms
7,936 KB
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 AC 3 ms
5,376 KB
testcase_17 RE -
testcase_18 RE -
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 8 ms
5,376 KB
testcase_21 AC 6 ms
5,376 KB
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 AC 4 ms
5,376 KB
testcase_26 AC 3 ms
5,376 KB
testcase_27 AC 5 ms
5,376 KB
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 AC 11 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifndef hari64
#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define debug(...)
#else
#include "util/viewer.hpp"
#define debug(...) viewer::_debug(__LINE__, #__VA_ARGS__, __VA_ARGS__)
#endif
// clang-format off
using namespace std;
using ll = long long; using ld = long double;
using pii = pair<int, int>; using pll = pair<ll, ll>;
template <typename T> using vc = vector<T>;
template <typename T> using vvc = vector<vc<T>>;
template <typename T> using vvvc = vector<vvc<T>>;
using vi = vc<int>; using vll = vc<ll>; using vpii = vc<pii>; using vpll = vc<pll>;
using vvi = vc<vi>; using vvll = vc<vll>; using vvpi = vc<vpii>; using vvpll = vc<vpll>;
#define ALL(x) begin(x), end(x)
#define RALL(x) (x).rbegin(), (x).rend()
constexpr int INF = 1001001001; constexpr long long INFll = 1001001001001001001;
template <class T> bool chmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template <class T> bool chmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
// clang-format on

#include <chrono>
struct Timer {
    void start() { _start = chrono::system_clock::now(); }
    void stop() {
        _end = chrono::system_clock::now();
        sum += chrono::duration_cast<chrono::nanoseconds>(_end - _start).count();
    }
    inline int ms() const {
        const chrono::system_clock::time_point now = chrono::system_clock::now();
        return static_cast<int>(
            chrono::duration_cast<chrono::microseconds>(now - _start).count() / 1000);
    }
    inline int ns() const {
        const chrono::system_clock::time_point now = chrono::system_clock::now();
        return static_cast<int>(
            chrono::duration_cast<chrono::microseconds>(now - _start).count());
    }
    string report() { return to_string(sum / 1000000) + "[ms]"; }
    void reset() {
        _start = chrono::system_clock::now();
        sum = 0;
    }

   private:
    chrono::system_clock::time_point _start, _end;
    long long sum = 0;
} timer;

int H, W, K, L, R;
vector<string> Ss;

pii simulateMove(const string& T) {
    assert(int(T.size()) <= K);
    int nowX = 0, nowY = 0;
    for (int i = 0; i < int(T.size()); i++) {
        if (T[i] == 'U')
            nowY--;
        else if (T[i] == 'D')
            nowY++;
        else if (T[i] == 'L')
            nowX--;
        else if (T[i] == 'R')
            nowX++;
        else {
            assert(false);
        }
        if (nowX < 0 || nowX >= W || nowY < 0 || nowY >= H) {
            return {-1, -1};
        }
        if (Ss[nowY][nowX] == '#') {
            return {-1, -1};
        }
        assert(Ss[nowY][nowX] == '.');
    }
    return {nowX, nowY};
}

bool isValidMovement(const string& T) {
    assert(int(T.size()) == K);
    pii res = simulateMove(T);
    int nowX = res.first, nowY = res.second;
    if (nowX == -1 && nowY == -1) return false;
    return nowX == W - 1 && nowY == H - 1;
}

bool isValidAnswer(const string& T) {
    if (!isValidMovement(T)) return false;
    debug(T);
    string partialyReversed = T;
    for (int i = L; i <= R; i++) {
        if (partialyReversed[i] == 'U')
            partialyReversed[i] = 'D';
        else if (partialyReversed[i] == 'D')
            partialyReversed[i] = 'U';
        else if (partialyReversed[i] == 'L')
            partialyReversed[i] = 'R';
        else if (partialyReversed[i] == 'R')
            partialyReversed[i] = 'L';
        else {
            assert(false);
        }
    }
    return isValidMovement(partialyReversed);
}

void slow() {
    string answer = "";
    string path = "";
    timer.start();
    auto dfs = [&](const auto& f) -> void {
        if (answer != "") return;
        if (timer.ms() >= 1800) {
            assert(false);
            return;
        }
        if (int(path.size()) == K) {
            if (isValidAnswer(path)) answer = path;
            return;
        }
        for (char c : {'U', 'D', 'L', 'R'}) {
            path.push_back(c);
            if (simulateMove(path) != pii(-1, -1)) {
                f(f);
            }
            path.pop_back();
        }
    };
    dfs(dfs);
    if (answer == "") {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
        cout << answer << endl;
    }
}

constexpr int DH[4] = {-1, 1, 0, 0};
constexpr int DW[4] = {0, 0, -1, 1};
vvi bfs_dist(int sh, int sw) {
    vvi dist(H, vi(W, -1));
    queue<pii> q;
    dist[sh][sw] = 0;
    q.push({sh, sw});
    while (!q.empty()) {
        pii v = q.front();
        q.pop();
        for (int d = 0; d < 4; d++) {
            int nh = v.first + DH[d];
            int nw = v.second + DW[d];
            if (nh < 0 || nh >= H || nw < 0 || nw >= W) continue;
            if (dist[nh][nw] != -1) continue;
            if (Ss[nh][nw] == '#') continue;
            dist[nh][nw] = dist[v.first][v.second] + 1;
            q.push({nh, nw});
        }
    }
    return dist;
}

string findPath(int sh, int sw, int gh, int gw) {
    vvi dist(H, vi(W, INF));
    vvc<char> prev(H, vc<char>(W, 'X'));
    queue<pii> q;
    assert(Ss[sh][sw] == '.');
    dist[sh][sw] = 0;
    q.push({sh, sw});
    while (!q.empty() && dist[gh][gw] == INF) {
        pii v = q.front();
        q.pop();
        for (int d = 0; d < 4; d++) {
            int nh = v.first + DH[d];
            int nw = v.second + DW[d];
            if (nh < 0 || nh >= H || nw < 0 || nw >= W) continue;
            if (dist[nh][nw] != INF) continue;
            if (Ss[nh][nw] == '#') continue;
            dist[nh][nw] = dist[v.first][v.second] + 1;
            prev[nh][nw] = "UDLR"[d];
            q.push({nh, nw});
        }
    }
    assert(dist[gh][gw] != INF);
    int nowH = gh;
    int nowW = gw;
    string path = "";
    while (prev[nowH][nowW] != 'X') {
        char p = prev[nowH][nowW];
        path.push_back(p);
        if (p == 'U')
            nowH++;
        else if (p == 'D')
            nowH--;
        else if (p == 'L')
            nowW++;
        else if (p == 'R')
            nowW--;
        else
            assert(false);
    };
    reverse(path.begin(), path.end());
    return path;
}

void fast() {
    if (L == 0 || R == K - 1) {
        cout << "No" << endl;
    }
    if ((R - L + 1) % 2 == 1) {
        cout << "No" << endl;
    }

    vvi distFromStart = bfs_dist(0, 0);
    vvi distFromGoal = bfs_dist(H - 1, W - 1);

    for (int h = 0; h < H; h++) {
        for (int w = 0; w < W; w++) {
            if (Ss[h][w] == '#') continue;
            if (distFromStart[h][w] == -1) continue;
            if (distFromStart[h][w] > L) continue;
            if ((L - distFromStart[h][w]) % 2 == 1) continue;
            if (distFromGoal[h][w] == -1) continue;
            if (distFromGoal[h][w] > K - R - 1) continue;
            if (!(distFromStart[h][w] + distFromGoal[h][w] <= K &&
                  (K - (distFromStart[h][w] + distFromGoal[h][w])) % 2 == 0)) {
                continue;
            }
            for (int d = 0; d < 4; d++) {
                int nh = h + DH[d];
                int nw = w + DW[d];
                if (nh < 0 || nh >= H || nw < 0 || nw >= W) continue;
                if (Ss[nh][nw] == '#') continue;
                {
                    cout << "Yes" << endl;
                    string path1 = findPath(0, 0, h, w);
                    string path3 = findPath(h, w, H - 1, W - 1);
                    string path2 = "";
                    for (int _ = 0;
                         _ < (K - (distFromStart[h][w] + distFromGoal[h][w])) / 2;
                         _++) {
                        path2.push_back("UDLR"[d]);
                        path2.push_back("DURL"[d]);
                    }
                    string answer = path1 + path2 + path3;
                    assert(isValidAnswer(answer));
                    cout << answer << endl;
                    return;
                }
            }
        }
    }
    cout << "No" << endl;
    return;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> H >> W >> K >> L >> R;
    assert(3 <= H && H <= 500);
    assert(3 <= W && W <= 500);
    assert(4 <= K && K <= 500000);
    assert(1 <= L && L <= R && R <= K);
    L--;
    R--;
    Ss.resize(H);
    for (int i = 0; i < H; i++) {
        cin >> Ss[i];
        assert(int(Ss[i].size()) == W);
        for (auto& s : Ss[i]) {
            assert(s == '.' || s == '#');
        }
    }
    assert(Ss[0][0] == '.' && Ss[H - 1][W - 1] == '.');

    // slow();
    fast();

    return 0;
}
0