結果

問題 No.2411 Reverse Directions
コンテスト
ユーザー mymelochan
提出日時 2023-08-11 23:25:48
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,921 bytes
コンパイル時間 194 ms
コンパイル使用メモリ 82,208 KB
実行使用メモリ 161,664 KB
最終ジャッジ日時 2024-11-18 18:53:04
合計ジャッジ時間 31,396 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 21 TLE * 8
権限があれば一括ダウンロードができます

ソースコード

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] == ".":
                    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((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((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