結果

問題 No.2411 Reverse Directions
コンテスト
ユーザー hari64
提出日時 2023-07-19 21:36:49
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 5,361 bytes
コンパイル時間 584 ms
コンパイル使用メモリ 13,056 KB
実行使用メモリ 34,444 KB
最終ジャッジ日時 2024-10-09 18:45:37
合計ジャッジ時間 20,414 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import time
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 not 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 toIdx(h, w):
    return h * W + w


def toPos(idx):
    return (idx // W, idx % W)


def bfs_dist(sh, sw):
    dist = [[-1] * W for _ in range(H)]
    q = Queue()
    dist[sh][sw] = 0
    q.put(toIdx(sh, sw))
    while not q.empty():
        v = q.get()
        h, w = toPos(v)
        for d in range(4):
            nh = h + DH[d]
            nw = w + DW[d]
            if nh < 0 or nh >= H or nw < 0 or nw >= W:
                continue
            if dist[nh][nw] != -1:
                continue
            if not Ss[nh][nw]:
                continue
            dist[nh][nw] = dist[h][w] + 1
            q.put(toIdx(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(toIdx(sh, sw))
    while q and dist[gh][gw] == INF:
        v = q.get()
        h, w = toPos(v)
        for d in range(4):
            nh = h + DH[d]
            nw = w + DW[d]
            if nh < 0 or nh >= H or nw < 0 or nw >= W:
                continue
            if dist[nh][nw] != INF:
                continue
            if not Ss[nh][nw]:
                continue
            dist[nh][nw] = dist[h][w] + 1
            prev[nh][nw] = "UDLR"[d]
            q.put(toIdx(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)

    print(time.time(), file=sys.stderr)

    for h in range(H):
        for w in range(W):
            if not 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 not 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 not 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():
    print(time.time(), file=sys.stderr)
    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([char == "." for char in s])
    assert Ss[0][0] and Ss[H - 1][W - 1]

    fast()


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