結果

問題 No.2411 Reverse Directions
ユーザー mymelochanmymelochan
提出日時 2023-08-11 23:52:48
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,968 bytes
コンパイル時間 223 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 99,712 KB
最終ジャッジ日時 2024-04-29 15:10:10
合計ジャッジ時間 6,290 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 50 ms
55,424 KB
testcase_01 AC 47 ms
55,296 KB
testcase_02 AC 46 ms
55,552 KB
testcase_03 AC 48 ms
55,296 KB
testcase_04 AC 90 ms
99,712 KB
testcase_05 AC 46 ms
55,680 KB
testcase_06 AC 41 ms
55,552 KB
testcase_07 AC 83 ms
81,064 KB
testcase_08 AC 42 ms
55,168 KB
testcase_09 AC 41 ms
55,296 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 45 ms
55,936 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 67 ms
70,912 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 45 ms
55,424 KB
testcase_20 WA -
testcase_21 AC 118 ms
77,824 KB
testcase_22 WA -
testcase_23 AC 47 ms
57,088 KB
testcase_24 WA -
testcase_25 AC 45 ms
56,192 KB
testcase_26 AC 66 ms
69,248 KB
testcase_27 AC 99 ms
77,376 KB
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 AC 129 ms
79,872 KB
権限があれば一括ダウンロードができます

ソースコード

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((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