Submission #521111

#	Time	Username	Problem	Language	Result	Execution time	Memory
521111		zaystev	Tracks in the Snow (BOI13_tracks)	Cpython 3	0 / 100	2107 ms	323772 KiB

tracks

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

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70