結果

問題 No.2411 Reverse Directions
コンテスト
ユーザー mymelochan
提出日時 2023-08-11 23:58:53
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 5,248 bytes
コンパイル時間 608 ms
コンパイル使用メモリ 82,572 KB
実行使用メモリ 107,044 KB
最終ジャッジ日時 2024-11-18 19:50:07
合計ジャッジ時間 6,070 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#############################################################

import sys
sys.setrecursionlimit(10**7)

from heapq import heappop,heappush
from collections import deque,defaultdict,Counter
from bisect import bisect_left, bisect_right
from itertools import product,combinations,permutations
from math import sin,cos
#from math import isqrt #DO NOT USE PyPy

ipt = sys.stdin.readline
iin = lambda :int(ipt())
lmin = lambda :list(map(int,ipt().split()))

inf = 1<<30
#############################################################

H,W,K,L,R = lmin()
S = [input() for _ in range(H)]

if (R-L)%2 == 0:
    print("No")
    exit()

costs = [[inf]*W for _ in range(H)]
costt = [[inf]*W for _ in range(H)]
costs[0][0] = 0
costt[H-1][W-1] = 0

d = [(-1,0),(0,-1),(1,0),(0,1)]
d1 = [(-1,0,"D"),(0,-1,"R"),(1,0,"U"),(0,1,"L")]
d2 = [(-1,0,"U"),(0,-1,"L"),(1,0,"D"),(0,1,"R")]
dq = deque([(0,0,0)])
while dq:
    i,j,c = dq.pop()
    for di,dj in d:
        ni,nj = i+di,j+dj
        if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == ".":
            if costs[ni][nj] != inf:
                continue

            costs[ni][nj] = c+1
            dq.appendleft((ni,nj,c+1))

dq = deque([(H-1,W-1,0)])
while dq:
    i,j,c = dq.pop()
    for di,dj in d:
        ni,nj = i+di,j+dj
        if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == ".":
            if costt[ni][nj] != inf:
                continue
            costt[ni][nj] = c+1
            dq.appendleft((ni,nj,c+1))

if costs[H-1][W-1] == inf:
    print("No")
    exit()
    
for i in range(H):
    for j in range(W):
        r1 = (i+j)%2
        r2 = (L-1)%2
        r3 = (K-R)%2
        r4 = (H+W-i-j)%2
        if r1 == r2 and r4 == r3:
            
            if L-1 >= costs[i][j] and K-R >= costt[i][j]:
                if 1 <= j < W-1 and S[i][j-1] == "." and S[i][j] == "." and S[i][j+1] == ".":
                    #print((i,j))
                    ci,cj = i,j
                    ans = []
                    while True:
                        #print(ci,cj)
                        if ci == 0 and cj == 0:
                            break
                        for di,dj,u in d1:
                            ni,nj = ci+di,cj+dj
                            if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == ".":
                                if costs[ni][nj] == costs[ci][cj]-1:
                                    ci = ni
                                    cj = nj
                                    ans.append(u)
                                    break
                    
                    #print(ans)
                    ans.reverse()

                    for _ in range((L-1-costs[i][j])//2):
                        ans.append("L")
                        ans.append("R")

                    for _ in range((R-L+1)//2):
                        ans.append("L")
                        ans.append("R")
                    #print(ans)
                    ci,cj = i,j
                    while True:
                        if ci == H-1 and cj == W-1:
                            break
                        for di,dj,u in d2:
                            ni,nj = ci+di,cj+dj
                            if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == ".":
                                if costt[ni][nj] == costt[ci][cj]-1:
                                    ci = ni
                                    cj = nj
                                    ans.append(u)
                                    break

                    print("Yes")
                    print("".join(ans))
                    exit()

                if 1 <= i < H-1 and S[i-1][j] == "." and S[i][j] == "." and S[i+1][j] == ".":
                    ci,cj = i,j
                    ans = []
                    while True:
                        if ci == 0 and cj == 0:
                            break
                        for di,dj,u in d1:
                            ni,nj = ci+di,cj+dj
                            if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == ".":
                                if costs[ni][nj] == costs[ci][cj]-1:
                                    ci = ni
                                    cj = nj
                                    ans.append(u)
                                    break
                    ans.reverse()

                    for _ in range((K-R-costt[i][j])//2):
                        ans.append("U")
                        ans.append("D")

                    for _ in range((R-L+1)//2):
                        ans.append("U")
                        ans.append("D")
                    
                    ci,cj = i,j
                    while True:
                        if ci == H-1 and cj == W-1:
                            break
                        for di,dj,u in d2:
                            ni,nj = ci+di,cj+dj
                            if 0 <= ni < H and 0 <= nj < W:
                                if costt[ni][nj] == costt[ci][cj]-1:
                                    ci = ni
                                    cj = nj
                                    ans.append(u)
                                    break

                    print("Yes")
                    print("".join(ans))
                    exit()

print("No")
0