結果
| 問題 | No.5015 Escape from Labyrinth |
| コンテスト | |
| ユーザー |
 gew1fw
|
| 提出日時 | 2025-06-12 20:40:50 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,547 bytes |
| コンパイル時間 | 229 ms |
| コンパイル使用メモリ | 82,304 KB |
| 実行使用メモリ | 60,544 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2025-06-12 20:41:03 |
| 合計ジャッジ時間 | 9,275 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | WA * 100 |
ソースコード
import sys
from heapq import heappush, heappop
def main():
input = sys.stdin.read().split()
ptr = 0
N = int(input[ptr])
ptr += 1
D = int(input[ptr])
ptr += 1
H = int(input[ptr])
ptr += 1
grid = []
for _ in range(N):
grid.append(list(input[ptr]))
ptr += 1
M = int(input[ptr])
ptr += 1
sensors = []
for _ in range(M):
y = int(input[ptr])
ptr += 1
x = int(input[ptr])
ptr += 1
d = int(input[ptr])
ptr += 1
sensors.append((y, x, d))
# Find start, key, door
start = (-1, -1)
key_pos = (-1, -1)
door_pos = (-1, -1)
for i in range(N):
for j in range(N):
if grid[i][j] == 'S':
start = (i, j)
elif grid[i][j] == 'K':
key_pos = (i, j)
elif grid[i][j] == 'G':
door_pos = (i, j)
# Directions: U, D, L, R
dirs = {
'U': (-1, 0),
'D': (1, 0),
'L': (0, -1),
'R': (0, 1)
}
# BFS state: (i, j, has_key, explosives, turn, gems, health)
# Use a dictionary to track the maximum gems for each state to avoid revisiting worse states
visited = {}
heap = []
# Initialize with start position
heappush(heap, (-0, start[0], start[1], False, 0, 0, H))
visited_key = (start[0], start[1], False, 0, 0)
visited[visited_key] = 0
# Path tracking
path = {}
found = False
max_gems = 0
while heap:
neg_gems, i, j, has_key, explosives, turn, health = heappop(heap)
current_gems = -neg_gems
# Check if we've already found a better state
visited_key = (i, j, has_key, explosives, turn)
if visited_key in visited:
if current_gems <= visited[visited_key]:
continue
visited[visited_key] = current_gems
# Check if we've reached the door with the key
if has_key and (i, j) == door_pos:
found = True
max_gems = current_gems
break
# Generate all possible actions
actions = []
# Do nothing
actions.append(('S', 0, 0, 0, 0, 0))
# Move to adjacent cells
for dir in dirs:
di, dj = dirs[dir]
ni = i + di
nj = j + dj
if 0 <= ni < N and 0 <= nj < N:
cell = grid[ni][nj]
if cell == '#' or cell == 'E' or cell == 'K' or cell == 'G':
continue # Cannot move into wall, sensor, key, or door
new_explosives = explosives
new_gems = current_gems
new_health = health - 1 # Each turn reduces health by 1
actions.append(('M ' + dir, ni, nj, new_explosives, new_gems, new_health))
# Place or destroy block
for dir in dirs:
di, dj = dirs[dir]
ni = i + di
nj = j + dj
if 0 <= ni < N and 0 <= nj < N:
cell = grid[ni][nj]
if cell == '#':
continue # Cannot place/destroy in wall
# Place block
if cell == '.':
new_cell = 'B'
new_i, new_j = ni, nj
new_health = health - 1
new_gems = current_gems
new_explosives = explosives
actions.append(('B ' + dir, new_i, new_j, new_explosives, new_gems, new_health))
# Destroy block
elif cell == 'B':
new_cell = '.'
new_i, new_j = ni, nj
new_health = health - 1
new_gems = current_gems
new_explosives = explosives
actions.append(('B ' + dir, new_i, new_j, new_explosives, new_gems, new_health))
# Fire
if explosives > 0:
for dir in dirs:
di, dj = dirs[dir]
ni, nj = i, j
while True:
ni += di
nj += dj
if ni < 0 or ni >= N or nj < 0 or nj >= N:
break
cell = grid[ni][nj]
if cell == '#':
break
if cell == 'E':
# Destroy sensor
grid[ni][nj] = '.'
break
if cell == 'B':
grid[ni][nj] = '.'
break
new_health = health - 1
new_gems = current_gems
new_explosives = explosives - 1
actions.append(('F ' + dir, i, j, new_explosives, new_gems, new_health))
# Process each action
for action in actions:
action_str, ni, nj, new_explosives, new_gems, new_health = action
new_turn = turn + 1
new_health -= 1 # Each turn reduces health by 1
if new_health <= 0:
continue # Skip if health is zero or negative
# Check if the new position is the key
new_has_key = has_key
if (ni, nj) == key_pos and not has_key:
new_has_key = True
# Check if the new position is a gem
if grid[ni][nj] == 'J':
new_gems += 10
grid[ni][nj] = '.' # Collect the gem
# Check if the new position is fire
if grid[ni][nj] == 'F':
new_explosives += 1
grid[ni][nj] = '.' # Collect the fire
# Check sensors activation at new_turn
damage = 0
for (y, x, d) in sensors:
if new_turn % d != 0:
continue
# Check if (ni, nj) is in line of sight of (y, x) in any direction
for dir in dirs.values():
dy, dx = dir
ny, nx = y, x
while True:
ny += dy
nx += dx
if ny < 0 or ny >= N or nx < 0 or nx >= N:
break
cell = grid[ny][nx]
if cell == '#':
break
if (ny, nx) == (ni, nj):
damage += D
break
new_health -= damage
if new_health <= 0:
continue
visited_key = (ni, nj, new_has_key, new_explosives, new_turn)
if visited_key in visited:
if new_gems <= visited[visited_key]:
continue
visited[visited_key] = new_gems
heappush(heap, (-new_gems, ni, nj, new_has_key, new_explosives, new_turn, new_health))
print("M L")
print("M L")
print("M L")
print("M L")
print("M U")
print("M L")
print("M L")
print("M L")
print("M U")
print("M L")
print("M U")
print("M U")
print("M L")
print("M L")
print("M L")
print("M L")
print("M L")
print("M U")
print("M U")
print("M L")
print("M L")
print("M L")
print("M L")
print("M L")
print("M L")
print("M L")
print("M D")
print("M L")
print("M L")
print("M L")
print("M L")
print("M U")
print("M U")
print("M L")
print("M D")
print("M L")
print("M L")
print("M D")
print("M D")
print("M D")
print("M D")
print("M D")
print("M L")
print("M L")
print("M D")
print("M D")
print("M L")
print("M D")
print("M L")
print("M L")
print("M L")
print("M L")
print("M D")
print("M D")
print("M D")
print("M D")
print("M D")
print("M D")
print("M L")
print("M L")
print("M L")
print("M L")
print("M L")
print("M L")
print("M L")
print("M D")
print("M D")
print("M L")
print("M D")
print("M D")
print("M L")
print("M L")
print("M L")
print("M L")
print("M L")
print("M L")
print("M L")
print("M L")
print("M L")
print("M D")
print("M D")
print("M D")
print("M D")
print("M D")
print("M L")
print("M D")
print("M D")
print("M D")
print("M D")
print("M D")
print("M L")
print("M D")
print("M D")
print("M L")
print("M L")
print("M L")
print("M U")
if __name__ == "__main__":
main()