#901226 (cLay) No.2411 Reverse Directions

• 問題: No.2411 Reverse Directions
• ユーザー: tails
• 提出日時: 2023-08-12 01:50:04
• 言語: cLay (20240104-1)
• 結果: AC
• 実行時間: 13 ms / 2,000 ms
• コード長: 1,323 bytes
• コンパイル時間: 3,008 ms
• コンパイル使用メモリ: 176,232 KB
• 実行使用メモリ: 6,912 KB
• 最終ジャッジ日時: 2024-04-29 16:33:47
• 合計ジャッジ時間: 4,608 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	4 ms; 5,376 KB
testcase_05	AC	1 ms; 5,376 KB
testcase_06	AC	1 ms; 5,376 KB
testcase_07	AC	6 ms; 5,888 KB
testcase_08	AC	1 ms; 5,376 KB
testcase_09	AC	1 ms; 5,376 KB
testcase_10	AC	12 ms; 6,912 KB
testcase_11	AC	2 ms; 5,376 KB
testcase_12	AC	13 ms; 5,888 KB
testcase_13	AC	5 ms; 5,376 KB
testcase_14	AC	7 ms; 5,760 KB
testcase_15	AC	3 ms; 5,376 KB
testcase_16	AC	3 ms; 5,376 KB
testcase_17	AC	5 ms; 5,376 KB
testcase_18	AC	3 ms; 5,376 KB
testcase_19	AC	2 ms; 5,376 KB
testcase_20	AC	5 ms; 5,376 KB
testcase_21	AC	5 ms; 5,376 KB
testcase_22	AC	10 ms; 5,504 KB
testcase_23	AC	8 ms; 5,376 KB
testcase_24	AC	13 ms; 5,760 KB
testcase_25	AC	3 ms; 5,376 KB
testcase_26	AC	2 ms; 5,376 KB
testcase_27	AC	5 ms; 5,376 KB
testcase_28	AC	8 ms; 5,376 KB
testcase_29	AC	13 ms; 6,016 KB
testcase_30	AC	10 ms; 5,504 KB
testcase_31	AC	9 ms; 5,376 KB

ソースコード

int h,w,k,l,r;
char s[512][512];
char z[6d5];
int d[512][512],e[][];
int q[2048];

void f(int sy,int sx,int d[512][512]){
	d[sy][sx]=1;
	int i=0,j=0;
	q[j++&2047]=sy;
	q[j++&2047]=sx;
	while(i<j){
		int y=q[i++&2047];
		int x=q[i++&2047];
		rep(a,4){
			int y2=y-(a==0)+(a==1);
			int x2=x-(a==2)+(a==3);
			if(y2>=0&&y2<h&&x2>=0&&x2<w&&s[y2][x2]=='.'&&!d[y2][x2]){
				d[y2][x2]=d[y][x]+1;
				q[j++&2047]=y2;
				q[j++&2047]=x2;
			}
		}
	}
}

void g(int y,int x,int d[512][512],int p,int t){
	while(d[y][x]!=1){
		rep(a,4){
			int y2=y-(a==0)+(a==1);
			int x2=x-(a==2)+(a==3);
			if(y2>=0&&y2<h&&x2>=0&&x2<w&&d[y2][x2]==d[y][x]-1){
				y=y2;
				x=x2;
				z[p]="UDLR"[t<0?a^1:a];
				p+=t;
				break;
			}
		}
	}
}

{
	rd(h,w,k,l,r,s(h));
	f(0,0,d);
	f(h-1,w-1,e);
	if(r-l+1&1||h+w+k&1||!e[0][0]){
		wt("No");
		exit(0);
	}
	rep(y,h){
		rep(x,w){
			if(x+y+l&1&&d[y][x]&&d[y][x]-1<=l-1&&e[y][x]-1<=k-r&&(y>0&&y<h-1&&d[y-1][x]&&d[y+1][x]||x>0&&x<w-1&&d[y][x-1]&&d[y][x+1])){
				g(y,x,d,d[y][x]-2,-1);
				g(y,x,e,k-e[y][x]+1,1);
				int p=d[y][x]-1;
				int n=k-d[y][x]-e[y][x]+2>>1;
				if(y>0&&y<h-1&&d[y-1][x]&&d[y+1][x]){
					rep(n){
						z[p++]='D';
						z[p++]='U';
					}
				}else{
					rep(n){
						z[p++]='R';
						z[p++]='L';
					}
				}
				wt("Yes");
				wt(z);
				exit(0);
			}
		}
	}
	wt("No");
}