結果

問題 No.5015 Escape from Labyrinth
ユーザー KlavisKlavis
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
testcase_47 WA -
testcase_48 WA -
testcase_49 WA -
testcase_50 WA -
testcase_51 WA -
testcase_52 WA -
testcase_53 WA -
testcase_54 WA -
testcase_55 WA -
testcase_56 WA -
testcase_57 WA -
testcase_58 WA -
testcase_59 WA -
testcase_60 WA -
testcase_61 WA -
testcase_62 WA -
testcase_63 WA -
testcase_64 WA -
testcase_65 WA -
testcase_66 WA -
testcase_67 WA -
testcase_68 WA -
testcase_69 WA -
testcase_70 WA -
testcase_71 WA -
testcase_72 WA -
testcase_73 WA -
testcase_74 WA -
testcase_75 WA -
testcase_76 WA -
testcase_77 WA -
testcase_78 WA -
testcase_79 WA -
testcase_80 WA -
testcase_81 WA -
testcase_82 WA -
testcase_83 WA -
testcase_84 WA -
testcase_85 WA -
testcase_86 WA -
testcase_87 WA -
testcase_88 WA -
testcase_89 WA -
testcase_90 WA -
testcase_91 WA -
testcase_92 WA -
testcase_93 WA -
testcase_94 WA -
testcase_95 WA -
testcase_96 WA -
testcase_97 WA -
testcase_98 WA -
testcase_99 WA -
権限があれば一括ダウンロードができます

ソースコード

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