結果

問題 No.5015 Escape from Labyrinth
ユーザー Klavis
提出日時 2023-04-15 13:11:47
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 146 ms / 3,000 ms
コード長 2,351 bytes
コンパイル時間 1,094 ms
コンパイル使用メモリ 86,640 KB
実行使用メモリ 77,324 KB
スコア 12,310
最終ジャッジ日時 2023-04-15 13:12:13
合計ジャッジ時間 18,378 ms
ジャッジサーバーID
（参考情報） 		judge16 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

grid_size = 60  # 迷宮の大きさ
max_hp = 1500  # 初期体力
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
dir = "UDLR"


class Enemy:
    def __init__(self, y, x, d, num):
        self.y = y
        self.x = x
        self.d = d
        self.num = num
        self.destroyed = False


def range_out(y, x):
    if y < 0 or y >= grid_size:
        return True
    if x < 0 or x >= grid_size:
        return True
    return False


def find_path(sy, sx, gy, gx, S):
    siz = len(S)
    dist = [[-1] * siz for _ in range(siz)]
    dist[sy][sx] = 0
    q = deque([(sy, sx)])
    while q:
        y, x = q.popleft()
        for k in range(4):
            ny = y + dy[k]
            nx = x + dx[k]
            if range_out(ny, nx):
                continue
            if dist[ny][nx] != -1:
                continue
            cell = S[ny][nx]
            if cell == '#' or cell == 'B' or cell == 'E':
                continue
            dist[ny][nx] = dist[y][x] + 1
            q.append((ny, nx))

    res = ""
    if dist[gy][gx] == -1:
        return res
    now_y, now_x, now_d = gy, gx, dist[gy][gx]
    while now_y != sy or now_x != sx:
        moved = False
        for k in range(4):
            new_y = now_y + dy[k]
            new_x = now_x + dx[k]
            if range_out(new_y, new_x):
                continue
            if dist[new_y][new_x] != now_d - 1:
                continue
            now_y, now_x = new_y, new_x
            now_d -= 1
            res += dir[k ^ 1]
            moved = True
            break
        assert moved
    return res[::-1]


def main():
    N, D, H = map(int, input().split())
    S = [input() for _ in range(N)]
    M = int(input())
    E = []
    for _ in range(M):
        y, x, d = map(int, input().split())
        E.append(Enemy(y, x, d, len(E)))

    ans = ""
    sy, sx, ky, kx, gy, gx = None, None, None, None, None, None
    for i in range(N):
        for j in range(N):
            if S[i][j] == 'S':
                sy, sx = i, j
            elif S[i][j] == 'K':
                ky, kx = i, j
            elif S[i][j] == 'G':
                gy, gx = i, j

    find_key = find_path(sy, sx, ky, kx, S)
    ans += find_key
    goal = find_path(ky, kx, gy, gx, S)
    ans += goal
    for c in ans:
        print("M", c)


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