結果

問題 No.2411 Reverse Directions
ユーザー 沙耶花
提出日時 2023-08-11 22:00:03
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 38 ms / 2,000 ms
コード長 2,606 bytes
コンパイル時間 4,289 ms
コンパイル使用メモリ 259,320 KB
最終ジャッジ日時 2025-02-16 01:23:26
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <stdio.h>
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf32 1000000001
#define Inf64 4000000000000000001
void ng(){
cout<<"No"<<endl;
exit(0);
}
vector<int> dx = {1,-1,0,0},dy = {0,0,1,-1};
string s = "DURL";
void bfs(vector<vector<int>> &d,vector<string> &S,int sx,int sy){
int h = d.size(),w = d[0].size();
d[sx][sy] = 0;
queue<pair<int,int>> Q;
Q.emplace(sx,sy);
while(Q.size()>0){
int x = Q.front().first;
int y = Q.front().second;
Q.pop();
rep(i,4){
int xx = x + dx[i],yy = y+dy[i];
if(xx<0||xx>=h||yy<0||yy>=w)continue;
if(S[xx][yy]=='#')continue;
if(d[xx][yy]!=Inf32)continue;
d[xx][yy] = d[x][y]+1;
Q.emplace(xx,yy);
}
}
}
int main(){
int h,w;
cin>>h>>w;
int K;
cin>>K;
int L,R;
cin>>L>>R;
vector<string> S(h);
rep(i,h)cin>>S[i];
if((R-L+1)%2==1)ng();
if((h+w)%2 != K%2)ng();
// cout<<'a'<<endl;
vector d0(h,vector<int>(w,Inf32));
auto d1 = d0;
bfs(d0,S,0,0);
//cout<<'b'<<endl;
bfs(d1,S,h-1,w-1);
//cout<<'c'<<endl;
rep(i,h){
rep(j,w){
if(d0[i][j]<=L-1 && d1[i][j]<=K-R && d0[i][j]%2==(L-1)%2){
int ok = -1;
for(int k=0;k<4;k+=2){
bool f = true;
rep(l,2){
int t = k + l;
int xx = i + dx[t],yy = j+dy[t];
if(xx<0||xx>=h||yy<0||yy>=w){
f = false;
break;
}
if(S[xx][yy]=='#')f = false;
}
if(f)ok = k;
}
if(ok==-1)continue;
cout<<"Yes"<<endl;
string temp = "";
int cx = i,cy = j;
while(cx!=0 || cy!=0){
//cout<<cx<<','<<cy<<endl;
rep(k,4){
//cout<<k<<endl;
int xx = cx + dx[k],yy = cy + dy[k];
if(xx<0||xx>=h||yy<0||yy>=w)continue;
if(d0[xx][yy]+1!=d0[cx][cy])continue;
//cout<<k<<endl;
temp += s[k^1];
//cout<<k<<endl;
cx = xx,cy = yy;
//cout<<k<<endl;
break;
}
//cout<<cx<<','<<cy<<endl;
}
reverse(temp.begin(),temp.end());
while(temp.size()!=R){
temp += s[ok];
temp += s[ok^1];
}
cx = i,cy = j;
int last = 0;
while(cx!=h-1 || cy!=w-1){
//cout<<cx<<",,"<<cy<<endl;
rep(k,4){
int xx = cx + dx[k],yy = cy + dy[k];
if(xx<0||xx>=h||yy<0||yy>=w)continue;
if(d1[xx][yy]+1!=d1[cx][cy])continue;
temp += s[k];
cx = xx,cy = yy;
last = k;
break;
}
}
while(temp.size()!=K){
temp += s[last^1];
temp += s[last];
}
cout<<temp<<endl;
return 0;
}
}
}
ng();
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0