結果

問題 No.5015 Escape from Labyrinth
コンテスト
ユーザー Klavis
提出日時 2023-04-15 14:00:48
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,026 bytes
コンパイル時間 492 ms
コンパイル使用メモリ 87,004 KB
実行使用メモリ 77,700 KB
スコア 0
最終ジャッジ日時 2023-04-15 14:01:13
合計ジャッジ時間 21,157 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 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, None, None
    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], now_y, now_x

# メイン処理
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, jy, jx, gy, gx = None, None, None, None, None, None, None, None

    # 迷宮の各セルをループして、スタート地点(S)、鍵の位置(K)、宝石の位置(J)、ゴール地点(G)の座標を取得する
    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] == 'J':
                jy, jx = i, j
            elif S[i][j] == 'G':
                gy, gx = i, j

    # スタート地点から鍵の位置までの経路を見つける
    find_key, current_y, current_x = find_path(sy, sx, ky, kx, S)
    ans += find_key

    # 鍵の位置からゴール地点までの経路を見つける
    goal, _, _ = find_path(current_y, current_x, gy, gx, S)
    ans += goal

    # 経路を出力する
    for c in ans:
        print("M", c)

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