結果

問題 No.2411 Reverse Directions
ユーザー 👑 Nachia
提出日時 2023-08-11 22:05:18
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,736 bytes
コンパイル時間 1,205 ms
コンパイル使用メモリ 91,920 KB
最終ジャッジ日時 2025-02-16 01:26:38
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 WA * 2 MLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

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;
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0