結果

問題 No.2411 Reverse Directions
ユーザー FromBooskaFromBooska
提出日時 2023-08-15 19:55:03
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,411 bytes
コンパイル時間 898 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 99,712 KB
最終ジャッジ日時 2024-05-03 06:39:52
合計ジャッジ時間 6,107 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
54,016 KB
testcase_01 AC 38 ms
54,272 KB
testcase_02 AC 39 ms
54,272 KB
testcase_03 AC 36 ms
54,400 KB
testcase_04 AC 76 ms
99,712 KB
testcase_05 AC 37 ms
54,272 KB
testcase_06 AC 40 ms
54,272 KB
testcase_07 AC 98 ms
78,812 KB
testcase_08 AC 39 ms
54,656 KB
testcase_09 AC 41 ms
54,272 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 74 ms
76,544 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 69 ms
70,784 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 41 ms
55,040 KB
testcase_20 WA -
testcase_21 AC 82 ms
77,312 KB
testcase_22 WA -
testcase_23 AC 85 ms
76,800 KB
testcase_24 WA -
testcase_25 AC 62 ms
71,552 KB
testcase_26 AC 38 ms
54,400 KB
testcase_27 AC 62 ms
73,472 KB
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 AC 84 ms
77,312 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も必要
# 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