結果

問題 No.2411 Reverse Directions
コンテスト
ユーザー FromBooska
提出日時 2023-08-15 19:55:03
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,411 bytes
コンパイル時間 277 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 99,840 KB
最終ジャッジ日時 2024-11-24 04:26:26
合計ジャッジ時間 5,938 ms
ジャッジサーバーID
（参考情報） 		judge5 / 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も必要
# WA、distance<=L-1までの場所で行ったり来たりすることもできるな

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])
                    
#print(distance)

def check(ch, cw):
    if L-1 - distance[ch][cw] < 0 or (L-1 - distance[ch][cw])%2==1:
        return -1
    
    # 行ったり来たりチェック
    L1_direction = -1 #縦0、横1
    back_forth_test = False
    if 1 <= ch < H-1 and S[ch-1][cw] == S[ch][cw] == S[ch+1][cw] == '.':
        back_forth_test = True
        L1_direction = 0
    if 1 <= cw < W-1 and S[ch][cw-1] == S[ch][cw] == S[ch][cw+1] == '.':
        back_forth_test = True
        L1_direction = 1
    if back_forth_test == False:
        return -1

    return L1_direction

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

for h in range(H):
    for w in range(W):
        dire = check(h, w)
        if dire == -1:
            continue
        
        direction1 = ['U', 'D', 'L', 'R']
        route1 = []
        current = (h, w)
        for i in range(L-1, -1, -1):
            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

        route2 = []
        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')        

        direction3 = ['D', 'U', 'R', 'L']
        route3 = []
        current = (h, w)
        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

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