| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 521110 | zaystev | Tracks in the Snow (BOI13_tracks) | Cpython 3 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
from collections import deque
m, n = map(int, input().strip().split())
grid = []
for _ in range(m):
grid.append(list(input().strip()))
q = deque([(0, 0)])
visited = set()
costs = [[float("inf")] * n for _ in range(m)]
costs[0][0] = 1
while q:
x, y = q.popleft()
if x == m - 1 and y == n - 1:
return costs[x][y]
visited.add((x, y))
for (dx, dy) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
n_x, n_y = x + dx, y + dy
if 0 <= n_x < m and 0 <= n_y < n and grid[n_x][n_y] != "." and (n_x, n_y) not in visited:
loss = 0 if grid[n_x][n_y] == grid[x][y] else 1
if loss + costs[x][y] < costs[n_x][n_y]:
costs[n_x][n_y] = loss + costs[x][y]
q.append((n_x, n_y)) if loss == 1 else q.appendleft((n_x, n_y))