結果

問題 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;
}
0