結果

問題 No.2411 Reverse Directions
コンテスト
ユーザー FromBooska
提出日時 2023-08-15 14:15:46
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,039 bytes
コンパイル時間 215 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 99,456 KB
最終ジャッジ日時 2024-11-23 21:43:13
合計ジャッジ時間 7,316 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16 WA * 13
権限があれば一括ダウンロードができます

ソースコード

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