Submission

Score: 100

User: SnowAveNode

Problemset: ย่องเบาหลบกับระเบิด

Language: python

Time: 2.294 second

Submitted On: 2026-04-11 19:58:40

import sys
input = sys.stdin.readline
from collections import deque

n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
dist = [[float('inf')]*m for _ in range(n)]

for i in range(n):
    for j in range(m):
        if grid[i][j] == 0:
            for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]:
                ny, nx = i + dy, j + dx

                if 0 <= ny < n and 0 <= nx < m and grid[ny][nx] == 1:
                    grid[ny][nx] = 2

queue = deque()
for i in range(n):
    if grid[i][0] == 1:
        queue.append((i, 0))
        dist[i][0] = 1

while queue:
    y, x = queue.popleft()
    
    for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        ny, nx = y + dy, x + dx

        if 0 <= ny < n and 0 <= nx < m and grid[ny][nx] == 1 and dist[ny][nx] == float('inf'):
            dist[ny][nx] = dist[y][x] + 1
            queue.append((ny, nx))

ans = float('inf')
for i in range(n):
    ans = min(ans, dist[i][m-1])

print(ans if ans != float('inf') else -1)