#893086 (Python3) No.2411 Reverse Directions

提出ソース

結果

問題	No.2411 Reverse Directions
ユーザー	hari64
提出日時	2023-07-19 21:19:28
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	TLE
実行時間	-
コード長	5,144 bytes
コンパイル時間	163 ms
コンパイル使用メモリ	13,312 KB
実行使用メモリ	32,564 KB
最終ジャッジ日時	2024-10-09 18:45:05
合計ジャッジ時間	20,121 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	35 ms 11,776 KB
testcase_01	AC	34 ms 11,648 KB
testcase_02	AC	35 ms 11,648 KB
testcase_03	AC	34 ms 11,776 KB
testcase_04	AC	327 ms 16,844 KB
testcase_05	AC	37 ms 11,776 KB
testcase_06	AC	35 ms 11,776 KB
testcase_07	AC	79 ms 16,000 KB
testcase_08	AC	35 ms 11,776 KB
testcase_09	AC	34 ms 11,776 KB
testcase_10	AC	1,929 ms 32,564 KB
testcase_11	AC	36 ms 11,776 KB
testcase_12	TLE	-
testcase_13	AC	38 ms 11,776 KB
testcase_14	AC	535 ms 16,064 KB
testcase_15	AC	184 ms 13,232 KB
testcase_16	AC	81 ms 11,904 KB
testcase_17	AC	632 ms 16,344 KB
testcase_18	AC	337 ms 14,392 KB
testcase_19	AC	36 ms 11,776 KB
testcase_20	AC	530 ms 14,776 KB
testcase_21	AC	353 ms 14,592 KB
testcase_22	AC	1,835 ms 22,896 KB
testcase_23	AC	37 ms 11,904 KB
testcase_24	TLE	-
testcase_25	AC	36 ms 11,776 KB
testcase_26	AC	78 ms 11,904 KB
testcase_27	AC	321 ms 13,056 KB
testcase_28	AC	1,037 ms 20,328 KB
testcase_29	AC	1,954 ms 26,748 KB
testcase_30	AC	1,720 ms 23,536 KB
testcase_31	AC	913 ms 18,304 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

yukicoder

結果

テストケース

ソースコード