#859977 (PyPy3) No.5015 Escape from Labyrinth

提出ソース

結果

問題	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
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	121 ms 76,768 KB
testcase_01	AC	120 ms 77,212 KB
testcase_02	AC	118 ms 76,932 KB
testcase_03	AC	119 ms 77,084 KB
testcase_04	AC	121 ms 77,112 KB
testcase_05	AC	118 ms 77,084 KB
testcase_06	AC	118 ms 77,308 KB
testcase_07	AC	143 ms 77,108 KB
testcase_08	AC	118 ms 77,132 KB
testcase_09	AC	120 ms 77,208 KB
testcase_10	AC	119 ms 77,104 KB
testcase_11	AC	120 ms 77,104 KB
testcase_12	AC	118 ms 77,284 KB
testcase_13	AC	119 ms 77,044 KB
testcase_14	AC	120 ms 77,108 KB
testcase_15	AC	144 ms 77,224 KB
testcase_16	AC	119 ms 77,148 KB
testcase_17	AC	121 ms 77,276 KB
testcase_18	AC	120 ms 77,096 KB
testcase_19	AC	117 ms 77,076 KB
testcase_20	AC	117 ms 77,264 KB
testcase_21	AC	121 ms 77,292 KB
testcase_22	AC	120 ms 77,224 KB
testcase_23	AC	142 ms 77,072 KB
testcase_24	AC	118 ms 76,904 KB
testcase_25	AC	117 ms 77,264 KB
testcase_26	AC	119 ms 77,080 KB
testcase_27	AC	120 ms 77,240 KB
testcase_28	AC	120 ms 77,052 KB
testcase_29	AC	120 ms 76,928 KB
testcase_30	AC	135 ms 77,092 KB
testcase_31	AC	121 ms 77,272 KB
testcase_32	AC	122 ms 77,080 KB
testcase_33	AC	120 ms 77,228 KB
testcase_34	AC	121 ms 77,236 KB
testcase_35	AC	118 ms 77,292 KB
testcase_36	AC	120 ms 77,092 KB
testcase_37	AC	118 ms 77,236 KB
testcase_38	AC	144 ms 77,232 KB
testcase_39	AC	117 ms 77,236 KB
testcase_40	AC	117 ms 77,048 KB
testcase_41	AC	120 ms 76,924 KB
testcase_42	AC	120 ms 77,172 KB
testcase_43	AC	121 ms 77,048 KB
testcase_44	AC	121 ms 77,088 KB
testcase_45	AC	121 ms 77,240 KB
testcase_46	AC	132 ms 77,084 KB
testcase_47	AC	120 ms 77,116 KB
testcase_48	AC	123 ms 77,060 KB
testcase_49	AC	119 ms 77,280 KB
testcase_50	AC	121 ms 77,080 KB
testcase_51	AC	119 ms 77,296 KB
testcase_52	AC	120 ms 77,164 KB
testcase_53	AC	122 ms 77,172 KB
testcase_54	AC	139 ms 77,240 KB
testcase_55	AC	119 ms 77,212 KB
testcase_56	AC	121 ms 77,276 KB
testcase_57	AC	118 ms 77,108 KB
testcase_58	AC	121 ms 77,056 KB
testcase_59	AC	122 ms 77,284 KB
testcase_60	AC	118 ms 77,208 KB
testcase_61	AC	121 ms 77,104 KB
testcase_62	AC	137 ms 77,176 KB
testcase_63	AC	119 ms 77,088 KB
testcase_64	AC	120 ms 77,076 KB
testcase_65	AC	117 ms 77,044 KB
testcase_66	AC	119 ms 77,136 KB
testcase_67	AC	119 ms 77,204 KB
testcase_68	AC	119 ms 77,092 KB
testcase_69	AC	119 ms 77,276 KB
testcase_70	AC	131 ms 77,220 KB
testcase_71	AC	117 ms 76,928 KB
testcase_72	AC	119 ms 76,772 KB
testcase_73	AC	119 ms 77,044 KB
testcase_74	AC	122 ms 77,052 KB
testcase_75	AC	118 ms 77,244 KB
testcase_76	AC	122 ms 77,224 KB
testcase_77	AC	146 ms 77,212 KB
testcase_78	AC	120 ms 77,080 KB
testcase_79	AC	121 ms 77,172 KB
testcase_80	AC	121 ms 77,244 KB
testcase_81	AC	121 ms 77,252 KB
testcase_82	AC	120 ms 77,232 KB
testcase_83	AC	119 ms 77,084 KB
testcase_84	AC	119 ms 77,324 KB
testcase_85	AC	144 ms 77,176 KB
testcase_86	AC	120 ms 77,088 KB
testcase_87	AC	118 ms 77,240 KB
testcase_88	AC	119 ms 77,204 KB
testcase_89	AC	120 ms 77,288 KB
testcase_90	AC	121 ms 77,240 KB
testcase_91	AC	120 ms 76,776 KB
testcase_92	AC	119 ms 77,056 KB
testcase_93	AC	141 ms 77,100 KB
testcase_94	AC	120 ms 77,292 KB
testcase_95	AC	120 ms 77,244 KB
testcase_96	AC	119 ms 77,076 KB
testcase_97	AC	119 ms 77,076 KB
testcase_98	AC	119 ms 76,912 KB
testcase_99	AC	120 ms 77,208 KB

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

ソースコード

raw source code

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

yukicoder

結果

テストケース

ソースコード