Submission #748309

#	Time	Username	Problem	Language	Result	Execution time	Memory
748309		54skyxenon	Tracks in the Snow (BOI13_tracks)	Pypy 3	65 / 100	2100 ms	389304 KiB

tracks

# https://oj.uz/problem/view/BOI13_tracks

from collections import deque

h, w = map(int, input().split())

grid = []
for _ in range(h):
    grid.append(input())

ans = 0
Q = deque([(0, 0, 1)])
seen = set()

while Q:
    r, c, depth = Q.popleft()
    seen.add((r, c))
    ans = max(ans, depth)

    for nr, nc in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]:
        if 0 <= nr < h and 0 <= nc < w and (nr, nc) not in seen and grid[nr][nc] != '.':
            if grid[nr][nc] == grid[r][c]:
                Q.appendleft((nr, nc, depth))
            else:
                Q.append((nr, nc, depth + 1))

print(ans)

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