結果

問題 No.2411 Reverse Directions
ユーザー 👑 NachiaNachia
提出日時 2023-08-11 22:05:18
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,736 bytes
コンパイル時間 1,052 ms
コンパイル使用メモリ 96,748 KB
実行使用メモリ 814,724 KB
最終ジャッジ日時 2024-11-18 16:26:58
合計ジャッジ時間 25,132 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <tuple>
#include <atcoder/modint>
using namespace std;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
const i64 INF = 1001001001001001001;

using Modint = atcoder::static_modint<998244353>;


int main(){
    int H,W,K,L,R; cin >> H >> W >> K >> L >> R; L--;
    vector<string> G(H); rep(y,H) cin >> G[y];
    if((R-L) % 2 == 1){ cout << "No\n"; return 0; }
    if((H+W)%2 != K%2){ cout << "No\n"; return 0; }
    tuple<int, int, char, int> dir[4] = {{1,0,'D',0},{-1,0,'U',1},{0,1,'R',2},{0,-1,'L',3}};

    auto getdist = [&](int sy, int sx){
        vector<pair<int,int>> que;
        vector pre(H, vector(W,-1)); pre[sy][sx] = -2;
        vector dist(H, vector(W,K+1));
        dist[sy][sx] = 0;
        que.push_back({sy,sx});
        rep(i,que.size()){
            auto [y,x] = que[i];
            for(auto [dy,dx,c,di] : dir){
                int nx = x + dx, ny = y + dy;
                if(nx < 0 || ny < 0 || nx >= W || ny >= H) continue;
                if(G[ny][nx] == '#') continue;
                if(pre[ny][ny] != -1) continue;
                pre[ny][nx] = di;
                dist[ny][nx] = dist[y][x] + 1;
                que.push_back({ ny,nx });
            }
        }
        return make_pair(move(dist), move(pre));
    };
    auto getpath = [&](int sy, int sx, int ty, int tx, const vector<vector<int>>& pre){
        vector<int> res;
        while(sy != ty || sx != tx){
            auto [dy,dx,c,di] = dir[pre[ty][tx]];
            res.push_back(di);
            ty -= dy; tx -= dx;
        }
        return res;
    };
    auto [dist0, pre0] = getdist(0,0);
    auto [dist1, pre1] = getdist(H-1,W-1);
    int ty=-1, tx=-1, td=-1;
    for(int y=0; y<H; y++) for(int x=0; x<W; x++) if(dist0[y][x] <= L && dist1[y][x] <= K-R){
        if(y!=0 && y!=H-1 && G[y-1][x] != '#' && G[y+1][x] != '#'){
            ty=y; tx=x; td=0; break;
        }
        if(x!=0 && x!=W-1 && G[y][x-1] != '#' && G[y][x+1] != '#'){
            ty=y; tx=x; td=2; break;
        }
    }
    if(ty < 0){ cout << "No\n"; return 0; }
    
    auto p0 = getpath(0, 0, ty, tx, pre0);
    auto p1 = getpath(H-1, W-1, ty, tx, pre1);
    reverse(p0.begin(), p0.end());
    int cnt = K - p0.size() - p1.size();
    rep(i,cnt) p0.push_back(td ^ (i%2));
    for(int x : p1) p0.push_back(x^1);

    cout << "Yes\n";
    rep(i,p0.size()){
        cout << (char)get<2>(dir[p0[i]]);
    } cout << '\n';

    return 0;
}


struct ios_do_not_sync{
    ios_do_not_sync(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    }
} ios_do_not_sync_instance;
0