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

• 問題: No.2411 Reverse Directions
• ユーザー: ococonomy1
• 提出日時: 2023-08-11 22:47:05
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 11,665 bytes
• コンパイル時間: 1,665 ms
• コンパイル使用メモリ: 135,876 KB
• 最終ジャッジ日時: 2025-02-16 01:53:48
• ジャッジサーバーID （参考情報）: judge4 / judge3

ファイルパターン	結果
sample	AC * 3
other	AC * 22 WA * 7

ソースコード

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
using lg = long long;
using pii = pair<int, int>;
using pll = pair<lg, lg>;
#define TEST cerr << "TEST" << endl
// #define AMARI 998244353
#define AMARI 1000000007
#define TEMOTO ((sizeof(long double) == 16) ? false : true)
#define TIME_LIMIT 1980 * (TEMOTO ? 1 : 1000)
#define mpr make_pair
#define el '\n'
#define El '\n'

#define MULTI_TEST_CASE false
void solve(void) {
    int h, w, k, l, r;
    cin >> h >> w >> k >> l >> r;
    vector<string> s(h);
    for(int i = 0; i < h; i++) cin >> s[i];
    if((r - l) % 2 == 0) {
        cout << "No" << el;
        return;
    }
    if(k % 2 != (h + w) % 2) {
        cout << "No" << el;
        return;
    }
    if((k - (r - l + 1)) - ((h - 1) + (w - 1)) < 0) {
        cout << "No" << el;
        return;
    }
    vector<vector<bool>> oufucu_tate(h, vector<bool>(w, false)),oufucu_yoko(h, vector<bool>(w, false)),oufucu(h, vector<bool>(w, false));
    vector<vector<bool>> kaiten_00(h,vector<bool>(w,false)),kaiten_01(h,vector<bool>(w,false)),kaiten_10(h,vector<bool>(w,false)),kaiten_11(h,vector<bool>(w,false));
    vector<vector<bool>> kaiten(h,vector<bool>(w,false));
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            if(i != 0 && i != h - 1 && s[i][j] == '.' && s[i - 1][j] == '.' && s[i + 1][j] == '.')oufucu_tate[i][j] = true;
            if(j != 0 && j != w - 1 && s[i][j] == '.' && s[i][j - 1] == '.' && s[i][j + 1] == '.')oufucu_yoko[i][j] = true;
            if(oufucu_tate[i][j] || oufucu_yoko[i][j]) oufucu[i][j] = true;

            if(i != h - 1 && j != w - 1 && s[i][j] == '.' && s[i + 1][j] == '.' && s[i][j + 1] == '.' && s[i + 1][j + 1] == '.'){
                kaiten_00[i][j] = true;
                kaiten_01[i][j + 1] = true;
                kaiten_10[i + 1][j] = true;
                kaiten_11[i + 1][j + 1] = true;
            }
            if(kaiten_00[i][j] || kaiten_01[i][j] || kaiten_10[i][j] || kaiten_11[i][j])kaiten[i][j] = true;
        }
    }

    // 左上からl-1回の移動で行けるoufucuがtrueの点を探す
    // secondについて、上から来た:1 下から来た:2 右から3 左から4
    vector<vector<pii>> dist00(h, vector<pii>(w, mpr(INT_MAX / 2, -1)));
    dist00[0][0] = mpr(0, 0);
    queue<pii> que;
    que.push(mpr(0, 0));
    while(!que.empty()) {
        int x, y;
        tie(x, y) = que.front();
        que.pop();
        if(x != 0 && s[x - 1][y] == '.' && dist00[x - 1][y].first > dist00[x][y].first + 1) {
            dist00[x - 1][y].first = dist00[x][y].first + 1;
            dist00[x - 1][y].second = 2;
            que.push(mpr(x - 1, y));
        }
        if(x != h - 1 && s[x + 1][y] == '.' && dist00[x + 1][y].first > dist00[x][y].first + 1) {
            dist00[x + 1][y].first = dist00[x][y].first + 1;
            dist00[x + 1][y].second = 1;
            que.push(mpr(x + 1, y));
        }
        if(y != 0 && s[x][y - 1] == '.' && dist00[x][y - 1].first > dist00[x][y].first + 1) {
            dist00[x][y - 1].first = dist00[x][y].first + 1;
            dist00[x][y - 1].second = 3;
            que.push(mpr(x, y - 1));
        }
        if(y != w - 1 && s[x][y + 1] == '.' && dist00[x][y + 1].first > dist00[x][y].first + 1) {
            dist00[x][y + 1].first = dist00[x][y].first + 1;
            dist00[x][y + 1].second = 4;
            que.push(mpr(x, y + 1));
        }
    }
    // 右下からk-r回の移動で行けるoufucuがtrueの点を探す
    // secondについて、上から来た:1 下から来た:2 右から3 左から4
    vector<vector<pii>> disthw(h, vector<pii>(w, mpr(INT_MAX / 2, -1)));
    disthw[h - 1][w - 1] = mpr(0, 0);
    while(!que.empty()) que.pop();
    que.push(mpr(h - 1, w - 1));
    while(!que.empty()) {
        int x, y;
        tie(x, y) = que.front();
        que.pop();
        if(x != 0 && s[x - 1][y] == '.' &&
           disthw[x - 1][y].first > disthw[x][y].first + 1) {
            disthw[x - 1][y].first = disthw[x][y].first + 1;
            disthw[x - 1][y].second = 2;
            que.push(mpr(x - 1, y));
        }
        if(x != h - 1 && s[x + 1][y] == '.' &&
           disthw[x + 1][y].first > disthw[x][y].first + 1) {
            disthw[x + 1][y].first = disthw[x][y].first + 1;
            disthw[x + 1][y].second = 1;
            que.push(mpr(x + 1, y));
        }
        if(y != 0 && s[x][y - 1] == '.' &&
           disthw[x][y - 1].first > disthw[x][y].first + 1) {
            disthw[x][y - 1].first = disthw[x][y].first + 1;
            disthw[x][y - 1].second = 3;
            que.push(mpr(x, y - 1));
        }
        if(y != w - 1 && s[x][y + 1] == '.' &&
           disthw[x][y + 1].first > disthw[x][y].first + 1) {
            disthw[x][y + 1].first = disthw[x][y].first + 1;
            disthw[x][y + 1].second = 4;
            que.push(mpr(x, y + 1));
        }
    }

    pii tyuucan = mpr(-1, -1);
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            // if(oufucu[i][j])cerr << i << j << el;
            if(dist00[i][j].first <= l - 1 && disthw[i][j].first <= k - r && oufucu[i][j] == true) {
                tyuucan = mpr(i, j);
                break;
            }
        }
        if(tyuucan.first != -1) break;
    }
    // cerr << dist00[1][1].first << ' ' << disthw[1][1].first << el;
    if(tyuucan.first == -1) {
        if((r - l + 1) % 4 != 0){
            cout << "No" << el;
            return;
        }
        pii siten = mpr(-1,-1);
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                if(dist00[i][j].first <= l - 1 && disthw[i][j].first <= k - r && kaiten[i][j] == true){
                    siten = mpr(i,j);
                    break;
                }
            }
            if(siten.first != -1)break;
        }
        if(siten.first == -1){
            //TEST;
            cout << "No" << el;
            return;
        }
        cout << "Yes" << el;
        string zenhan, kouhan;
        pii temp = siten;
        while(temp.first != 0 || temp.second != 0) {
            if(dist00[temp.first][temp.second].second == 4) {
                zenhan.push_back('R');
                temp.second--;
                continue;
            }
            if(dist00[temp.first][temp.second].second == 3) {
                zenhan.push_back('L');
                temp.second++;
                continue;
            }
            if(dist00[temp.first][temp.second].second == 2) {
                zenhan.push_back('U');
                temp.first++;
                continue;
            }
            if(dist00[temp.first][temp.second].second == 1) {
                zenhan.push_back('D');
                temp.first--;
                continue;
            }
        }
        //cerr << siten.first << siten.second << el;
        for(int i = zenhan.size() - 1; i >= 0; i--) cout << zenhan[i];
        //ここで回転の出力をやる
        if(kaiten_00[siten.first][siten.second]){
            int cnt = k - dist00[siten.first][siten.second].first - disthw[siten.first][siten.second].first;
            for(int i = 0; i < cnt / 4; i++) cout << "DRUL";
        }
        else if(kaiten_01[siten.first][siten.second]){
            int cnt = k - dist00[siten.first][siten.second].first - disthw[siten.first][siten.second].first;
            for(int i = 0; i < cnt / 4; i++) cout << "DLUR";
        }
        else if(kaiten_10[siten.first][siten.second]){
            int cnt = k - dist00[siten.first][siten.second].first - disthw[siten.first][siten.second].first;
            for(int i = 0; i < cnt / 4; i++) cout << "URDL";
        }
        else{
            int cnt = k - dist00[siten.first][siten.second].first - disthw[siten.first][siten.second].first;
            for(int i = 0; i < cnt / 4; i++) cout << "ULDR";
        }
        temp = siten;
        // secondについて、上から来た:1 下から来た:2 右から3 左から4
        while(temp.first != h - 1 || temp.second != w - 1) {
            //cerr << temp.first << ' ' << temp.second << el;
            if(disthw[temp.first][temp.second].second == 4) {
                kouhan.push_back('L');
                temp.second--;
                continue;
            }
            if(disthw[temp.first][temp.second].second == 3) {
                kouhan.push_back('R');
                temp.second++;
                continue;
            }
            if(disthw[temp.first][temp.second].second == 2) {
                kouhan.push_back('D');
                temp.first++;
                continue;
            }
            if(disthw[temp.first][temp.second].second == 1) {
                kouhan.push_back('U');
                temp.first--;
                continue;
            }
        }
        for(int i = 0; i < kouhan.size(); i++) cout << kouhan[i];
        cout << el;
        return;
    }

    cout << "Yes" << el;
    string zenhan, kouhan;
    pii temp = tyuucan;
    // secondについて、上から来た:1 下から来た:2 右から3 左から4
    while(temp.first != 0 || temp.second != 0) {
        if(dist00[temp.first][temp.second].second == 4) {
            zenhan.push_back('R');
            temp.second--;
            continue;
        }
        if(dist00[temp.first][temp.second].second == 3) {
            zenhan.push_back('L');
            temp.second++;
            continue;
        }
        if(dist00[temp.first][temp.second].second == 2) {
            zenhan.push_back('U');
            temp.first++;
            continue;
        }
        if(dist00[temp.first][temp.second].second == 1) {
            zenhan.push_back('D');
            temp.first--;
            continue;
        }
    }
    for(int i = zenhan.size() - 1; i >= 0; i--) cout << zenhan[i];
    if(oufucu_tate[tyuucan.first][tyuucan.second]) {
        int cnt = k - dist00[tyuucan.first][tyuucan.second].first - disthw[tyuucan.first][tyuucan.second].first;
        for(int i = 0; i < cnt / 2; i++) cout << "UD";
    } else {
        int cnt = k - dist00[tyuucan.first][tyuucan.second].first - disthw[tyuucan.first][tyuucan.second].first;
        for(int i = 0; i < cnt / 2; i++) cout << "LR";
    }
    temp = tyuucan;
    int ccnt = 0;
    // secondについて、上から来た:1 下から来た:2 右から3 左から4
    while(temp.first != h - 1 || temp.second != w - 1) {
        //cerr << temp.first << ' ' << temp.second << el;
        if(disthw[temp.first][temp.second].second == 4) {
            kouhan.push_back('L');
            temp.second--;
            continue;
        }
        if(disthw[temp.first][temp.second].second == 3) {
            kouhan.push_back('R');
            temp.second++;
            continue;
        }
        if(disthw[temp.first][temp.second].second == 2) {
            kouhan.push_back('D');
            temp.first++;
            continue;
        }
        if(disthw[temp.first][temp.second].second == 1) {
            kouhan.push_back('U');
            temp.first--;
            continue;
        }
    }
    for(int i = 0; i < kouhan.size(); i++) cout << kouhan[i];
    cout << el;
    return;
}

void calc(void) {
    return;
}

int main(void) {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    calc();
    int t = 1;
    if(MULTI_TEST_CASE) cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}