結果

問題 No.2411 Reverse Directions
ユーザー hari64hari64
提出日時 2023-07-19 18:35:53
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 4,796 bytes
コンパイル時間 2,501 ms
コンパイル使用メモリ 211,988 KB
実行使用メモリ 13,640 KB
最終ジャッジ日時 2024-10-09 18:41:47
合計ジャッジ時間 7,901 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
13,640 KB
testcase_01 AC 1,514 ms
6,816 KB
testcase_02 AC 9 ms
6,816 KB
testcase_03 AC 2 ms
6,820 KB
testcase_04 TLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
権限があれば一括ダウンロードができます

ソースコード

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 vl = vc<ll>; using vpi = vc<pii>; using vpl = vc<pll>;
#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);
        }
    }
    debug(partialyReversed);
    return isValidMovement(partialyReversed);
}

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

void slow() {
    string answer = "";
    string path = "";
    timer.start();
    auto dfs = [&](const auto& f) -> void {
        if (answer != "") return;
        if (timer.ms() >= 1500) 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;
    }
}

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