Submission #521117

#	Time	Username	Problem	Language	Result	Execution time	Memory
521117		zaystev	Tracks in the Snow (BOI13_tracks)	Cpython 3	49.69 / 100	2101 ms	311188 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
ans = 1

while q:
	x, y = q.popleft()
	ans = max(ans, 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))
print(ans)

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