結果

問題 No.2411 Reverse Directions
ユーザー hari64hari64
提出日時 2023-07-19 21:19:28
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
TLE  
実行時間 -
コード長 5,144 bytes
コンパイル時間 96 ms
コンパイル使用メモリ 13,440 KB
実行使用メモリ 32,568 KB
最終ジャッジ日時 2024-04-18 01:01:02
合計ジャッジ時間 17,683 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 33 ms
11,648 KB
testcase_01 AC 29 ms
11,776 KB
testcase_02 AC 31 ms
11,648 KB
testcase_03 AC 32 ms
11,520 KB
testcase_04 AC 282 ms
16,996 KB
testcase_05 AC 29 ms
11,776 KB
testcase_06 AC 29 ms
11,776 KB
testcase_07 AC 69 ms
15,872 KB
testcase_08 AC 30 ms
11,648 KB
testcase_09 AC 31 ms
11,648 KB
testcase_10 AC 1,701 ms
32,568 KB
testcase_11 AC 32 ms
11,776 KB
testcase_12 TLE -
testcase_13 AC 33 ms
11,904 KB
testcase_14 AC 466 ms
16,068 KB
testcase_15 AC 161 ms
13,364 KB
testcase_16 AC 69 ms
12,032 KB
testcase_17 AC 546 ms
16,352 KB
testcase_18 AC 288 ms
14,264 KB
testcase_19 AC 30 ms
11,776 KB
testcase_20 AC 458 ms
14,900 KB
testcase_21 AC 310 ms
14,592 KB
testcase_22 AC 1,615 ms
22,876 KB
testcase_23 AC 33 ms
11,776 KB
testcase_24 TLE -
testcase_25 AC 31 ms
11,648 KB
testcase_26 AC 67 ms
11,904 KB
testcase_27 AC 277 ms
13,056 KB
testcase_28 AC 897 ms
20,356 KB
testcase_29 AC 1,732 ms
26,880 KB
testcase_30 AC 1,508 ms
23,368 KB
testcase_31 AC 816 ms
18,304 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from queue import Queue

DH = [-1, 1, 0, 0]
DW = [0, 0, -1, 1]
INF = 1001001001

H = -1
W = -1
K = -1
L = -1
R = -1
Ss = None


def simulateMove(T):
    assert len(T) <= K
    nowX, nowY = 0, 0
    for move in T:
        if move == "U":
            nowY -= 1
        elif move == "D":
            nowY += 1
        elif move == "L":
            nowX -= 1
        elif move == "R":
            nowX += 1
        else:
            assert False
        if nowX < 0 or nowX >= W or nowY < 0 or nowY >= H:
            return (-1, -1)
        if Ss[nowY][nowX] == "#":
            return (-1, -1)
        assert Ss[nowY][nowX] == "."
    return (nowX, nowY)


def isValidMovement(T):
    assert len(T) == K
    res = simulateMove(T)
    nowX, nowY = res
    if nowX == -1 and nowY == -1:
        return False
    return nowX == W - 1 and nowY == H - 1


def isValidAnswer(T):
    if not isValidMovement(T):
        return False
    partialyReversed = list(T)
    for i in range(L, R + 1):
        if partialyReversed[i] == "U":
            partialyReversed[i] = "D"
        elif partialyReversed[i] == "D":
            partialyReversed[i] = "U"
        elif partialyReversed[i] == "L":
            partialyReversed[i] = "R"
        elif partialyReversed[i] == "R":
            partialyReversed[i] = "L"
        else:
            assert False
    return isValidMovement("".join(partialyReversed))


def bfs_dist(sh, sw):
    dist = [[-1] * W for _ in range(H)]
    q = Queue()
    dist[sh][sw] = 0
    q.put((sh, sw))
    while not q.empty():
        v = q.get()
        for d in range(4):
            nh = v[0] + DH[d]
            nw = v[1] + DW[d]
            if nh < 0 or nh >= H or nw < 0 or nw >= W:
                continue
            if dist[nh][nw] != -1:
                continue
            if Ss[nh][nw] == "#":
                continue
            dist[nh][nw] = dist[v[0]][v[1]] + 1
            q.put((nh, nw))
    return dist


def findPath(sh, sw, gh, gw):
    dist = [[INF] * W for _ in range(H)]
    prev = [["X"] * W for _ in range(H)]
    q = Queue()
    assert Ss[sh][sw] == "."
    dist[sh][sw] = 0
    q.put((sh, sw))
    while q and dist[gh][gw] == INF:
        v = q.get()
        for d in range(4):
            nh = v[0] + DH[d]
            nw = v[1] + DW[d]
            if nh < 0 or nh >= H or nw < 0 or nw >= W:
                continue
            if dist[nh][nw] != INF:
                continue
            if Ss[nh][nw] == "#":
                continue
            dist[nh][nw] = dist[v[0]][v[1]] + 1
            prev[nh][nw] = "UDLR"[d]
            q.put((nh, nw))
    assert dist[gh][gw] != INF
    nowH, nowW = gh, gw
    path = ""
    while prev[nowH][nowW] != "X":
        p = prev[nowH][nowW]
        path += p
        if p == "U":
            nowH += 1
        elif p == "D":
            nowH -= 1
        elif p == "L":
            nowW += 1
        elif p == "R":
            nowW -= 1
        else:
            assert False
    return path[::-1]


def fast():
    if L == 0 or R == K - 1:
        print("No")
        return
    if (R - L + 1) % 2 == 1:
        print("No")
        return

    distFromStart = bfs_dist(0, 0)
    distFromGoal = bfs_dist(H - 1, W - 1)

    for h in range(H):
        for w in range(W):
            if Ss[h][w] == "#":
                continue
            if distFromStart[h][w] == -1:
                continue
            if distFromGoal[h][w] == -1:
                continue
            if (K - (distFromStart[h][w] + distFromGoal[h][w])) % 2 == 1:
                continue
            if distFromStart[h][w] > L:
                continue
            if distFromGoal[h][w] > K - 1 - R:
                continue
            for d in range(4):
                nh1 = h + DH[d]
                nw1 = w + DW[d]
                if nh1 < 0 or nh1 >= H or nw1 < 0 or nw1 >= W:
                    continue
                if Ss[nh1][nw1] == "#":
                    continue
                nh2 = h + DH[d ^ 1]
                nw2 = w + DW[d ^ 1]
                if nh2 < 0 or nh2 >= H or nw2 < 0 or nw2 >= W:
                    continue
                if Ss[nh2][nw2] == "#":
                    continue
                path1 = findPath(0, 0, h, w)
                path3 = findPath(h, w, H - 1, W - 1)
                path2 = ""
                for _ in range((K - (distFromStart[h][w] + distFromGoal[h][w])) // 2):
                    path2 += "UDLR"[d] + "DURL"[d]
                answer = path1 + path2 + path3
                if isValidAnswer(answer):
                    print("Yes")
                    print(answer)
                    return
    print("No")
    return


def main():
    global H, W, K, L, R, Ss
    H, W, K, L, R = map(int, input().split())
    assert 3 <= H <= 500
    assert 3 <= W <= 500
    assert 4 <= K <= 500000
    assert 1 <= L <= R <= K
    L -= 1
    R -= 1
    Ss = []
    for i in range(H):
        s = input().strip()
        assert len(s) == W
        for char in s:
            assert char == "." or char == "#"
        Ss.append(s)
    assert Ss[0][0] == "." and Ss[H - 1][W - 1] == "."

    fast()


if __name__ == "__main__":
    main()
0