結果

問題 No.2411 Reverse Directions
ユーザー kotatsugamekotatsugame
提出日時 2023-08-11 21:48:10
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 20 ms / 2,000 ms
コード長 1,927 bytes
コンパイル時間 810 ms
コンパイル使用メモリ 82,052 KB
実行使用メモリ 5,784 KB
最終ジャッジ日時 2024-11-18 15:51:02
合計ジャッジ時間 2,459 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<algorithm>
#include<queue>
#include<cassert>
using namespace std;
int H,W,K,L,R;
string S[500];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
string dir="RDLU";
int dist[2][500][500];
string f(int t,int i,int j)
{
	string ret="";
	while(dist[t][i][j]>0)
	{
		for(int r=0;r<4;r++)
		{
			if(t==0)
			{
				int x=i-dx[r],y=j-dy[r];
				if(x>=0&&y>=0&&x<H&&y<W&&dist[t][x][y]==dist[t][i][j]-1)
				{
					i=x,j=y;
					ret+=dir[r];
					break;
				}
			}
			else
			{
				int x=i+dx[r],y=j+dy[r];
				if(x>=0&&y>=0&&x<H&&y<W&&dist[t][x][y]==dist[t][i][j]-1)
				{
					i=x,j=y;
					ret+=dir[r];
					break;
				}
			}
		}
	}
	return ret;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>H>>W>>K>>L>>R;L--;
	for(int i=0;i<H;i++)cin>>S[i];
	if((R-L)%2==1)
	{
		cout<<"No"<<endl;
		return 0;
	}
	for(int t=0;t<2;t++)
	{
		for(int i=0;i<H;i++)for(int j=0;j<W;j++)dist[t][i][j]=1e9;
		queue<pair<int,int> >Q;
		if(t==0)
		{
			dist[t][0][0]=0;
			Q.push(make_pair(0,0));
		}
		else
		{
			dist[t][H-1][W-1]=0;
			Q.push(make_pair(H-1,W-1));
		}
		while(!Q.empty())
		{
			int x=Q.front().first,y=Q.front().second;
			Q.pop();
			for(int r=0;r<4;r++)
			{
				int tx=x+dx[r],ty=y+dy[r];
				if(tx<0||ty<0||tx>=H||ty>=W||S[tx][ty]=='#'||dist[t][tx][ty]<=dist[t][x][y]+1)continue;
				dist[t][tx][ty]=dist[t][x][y]+1;
				Q.push(make_pair(tx,ty));
			}
		}
	}
	for(int i=0;i<H;i++)for(int j=0;j<W;j++)if(S[i][j]=='.')
	{
		bool X=false,Y=false;
		if(i>0&&i+1<H&&S[i-1][j]=='.'&&S[i+1][j]=='.')X=true;
		if(j>0&&j+1<W&&S[i][j-1]=='.'&&S[i][j+1]=='.')Y=true;
		if(!X&&!Y)continue;
		int b=L-dist[0][i][j],a=K-R-dist[1][i][j];
		if(b<0||b%2==1||a<0||a%2==1)continue;
		cout<<"Yes\n";
		string B=f(0,i,j);
		reverse(B.begin(),B.end());
		cout<<B;
		int c=a+b+R-L;
		for(int t=0;t<c;t+=2)
		{
			cout<<(X?"DU":"LR");
		}
		string A=f(1,i,j);
		cout<<A<<endl;
		return 0;
	}
	cout<<"No"<<endl;
}
0