結果

問題 No.2411 Reverse Directions
ユーザー FromBooskaFromBooska
提出日時 2023-08-15 14:15:46
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,039 bytes
コンパイル時間 156 ms
コンパイル使用メモリ 82,276 KB
実行使用メモリ 99,584 KB
最終ジャッジ日時 2024-05-03 01:40:41
合計ジャッジ時間 5,924 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
54,144 KB
testcase_01 AC 41 ms
54,400 KB
testcase_02 AC 42 ms
54,272 KB
testcase_03 AC 43 ms
54,272 KB
testcase_04 AC 87 ms
99,584 KB
testcase_05 AC 44 ms
54,524 KB
testcase_06 AC 46 ms
54,272 KB
testcase_07 AC 66 ms
71,680 KB
testcase_08 AC 41 ms
54,016 KB
testcase_09 AC 43 ms
53,888 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 81 ms
76,416 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 70 ms
71,936 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 45 ms
54,912 KB
testcase_20 WA -
testcase_21 AC 91 ms
77,184 KB
testcase_22 WA -
testcase_23 AC 94 ms
77,312 KB
testcase_24 WA -
testcase_25 AC 69 ms
71,936 KB
testcase_26 AC 45 ms
60,160 KB
testcase_27 AC 74 ms
74,404 KB
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 AC 102 ms
77,696 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# BFS, distance
# L-1歩とR歩では同じ座標にいる、そうしないとゴールに行けない
# L to Rでは同じところを行ったり来たりすればいい、それ以上の動き必要なしだから
# つまりL-1歩で3個の縦または横のフリーゾーンの真ん中にいる必要
# (R+1-L)%2==0が必要
# (K-goal_distance-(R+1-L))%2==0も必要

H, W, K, L, R = map(int, input().split())
S = []
for i in range(H):
    s = input()
    S.append(s)

from collections import deque
d = [[+1, 0], [-1, 0], [0, +1], [0, -1]]
 
sh, sw = 0, 0
que = deque()
que.append((sh, sw))
INF = 10**4
distance = [[INF]*W for h in range(H)]
distance[sh][sw] = 0

while que:
    ch, cw = que.popleft()

    for dh, dw in d:
        if 0 <= ch+dh < H and 0 <= cw+dw < W:
            if S[ch+dh][cw+dw] != '#':
                if distance[ch+dh][cw+dw] > distance[ch][cw]+1:
                    distance[ch+dh][cw+dw] = distance[ch][cw]+1
                    que.append([ch+dh, cw+dw])

# 行ったり来たりチェック
L1_position = (-1, -1, -1) #第3は縦0、横1
back_forth_test = False
for h in range(H):
    for w in range(W):
        if distance[h][w] == L-1:
            if 1 <= h < H-1 and S[h-1][w] == S[h][w] == S[h+1][w] == '.':
                back_forth_test = True
                L1_position = (h, w, 0)
            if 1 <= w < W-1 and S[h][w-1] == S[h][w] == S[h][w+1] == '.':
                back_forth_test = True
                L1_position = (h, w, 1)
if back_forth_test == False:
    print('No')
    exit()
goal_distance = distance[H-1][W-1]
if goal_distance == INF:
    print('No')
    exit()
LR = R+1-L
if LR%2 == 1:
    print('No')
    exit()
if K-goal_distance-LR < 0 or (K-goal_distance-LR)%2 == 1:
    print('No')
    exit()
#print('L1_position', L1_position)


direction1 = ['U', 'D', 'L', 'R']

route1 = []
current = (L1_position[0], L1_position[1])
for i in range(L-1, -1, -1):
    #print('current', current)
    ch, cw = current
    for j in range(4):
        dh, dw = d[j]
        
        if 0 <= ch+dh < H and 0 <= cw+dw < W:
            if distance[ch+dh][cw+dw] == i-1:
                current = (ch+dh, cw+dw)
                route1.append(direction1[j])
                break

#print(route1)

route2 = []
l1h, l1w, dire = L1_position
if dire == 0:
    for k in range(LR//2):
        route2.append('U')
        route2.append('D')
elif dire == 1:
    for k in range(LR//2):
        route2.append('R')
        route2.append('L')        
#print(route2)

direction3 = ['D', 'U', 'R', 'L']
route3 = []
current = (L1_position[0], L1_position[1])
for i in range(L-1, goal_distance):
    #print('current', current)
    ch, cw = current
    for j in range(4):
        dh, dw = d[j]
        
        if 0 <= ch+dh < H and 0 <= cw+dw < W:
            if distance[ch+dh][cw+dw] == i+1:
                current = (ch+dh, cw+dw)
                route3.append(direction3[j])
                break

#print(route3)

ans = ''.join(route1[::-1]) + ''.join(route2) + ''.join(route3) 
print('Yes')
print(ans)
0