#893075 (C++17) No.2411 Reverse Directions

提出ソース

結果

問題	No.2411 Reverse Directions
ユーザー	hari64
提出日時	2023-07-19 20:11:38
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	RE
実行時間	-
コード長	8,378 bytes
コンパイル時間	3,302 ms
コンパイル使用メモリ	229,648 KB
実行使用メモリ	13,636 KB
最終ジャッジ日時	2024-10-09 18:43:26
合計ジャッジ時間	7,291 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 13,636 KB
testcase_01	RE	-
testcase_02	AC	2 ms 6,820 KB
testcase_03	AC	2 ms 6,820 KB
testcase_04	AC	32 ms 6,816 KB
testcase_05	RE	-
testcase_06	AC	2 ms 6,816 KB
testcase_07	AC	5 ms 6,820 KB
testcase_08	AC	2 ms 6,816 KB
testcase_09	AC	2 ms 6,816 KB
testcase_10	AC	19 ms 7,936 KB
testcase_11	AC	2 ms 6,820 KB
testcase_12	AC	30 ms 6,816 KB
testcase_13	TLE	-
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	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
    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 (distFromGoal[h][w] == -1) continue;
            for (int d = 0; d < 4; d++) {
                int nh1 = h + DH[d];
                int nw1 = w + DW[d];
                if (nh1 < 0 || nh1 >= H || nw1 < 0 || nw1 >= W) continue;
                if (Ss[nh1][nw1] == '#') continue;
                int nh2 = h + DH[d ^ 1];
                int nw2 = w + DW[d ^ 1];
                if (nh2 < 0 || nh2 >= H || nw2 < 0 || nw2 >= W) continue;
                if (Ss[nh2][nw2] == '#') continue;
                {
                    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;
                    if (isValidAnswer(answer)) {
                        cout << "Yes" << endl;
                        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;
}

yukicoder

結果

テストケース

ソースコード