結果

問題 No.2411 Reverse Directions
ユーザー mymelochanmymelochan
提出日時 2023-08-11 23:21:17
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,864 bytes
コンパイル時間 165 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 137,472 KB
最終ジャッジ日時 2024-04-29 14:32:13
合計ジャッジ時間 6,639 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 TLE -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
権限があれば一括ダウンロードができます

ソースコード

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,"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,u 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,u 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(1,H-1):
    for j in range(1,W-1):
        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 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 d:
                            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 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 d:
                            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