Submission #748295

#	Time	Username	Problem	Language	Result	Execution time	Memory
748295		54skyxenon	Tracks in the Snow (BOI13_tracks)	Cpython 3	23.65 / 100	2095 ms	75328 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())

def invert(c):
    return 'R' if c == 'F' else 'F'

tracks = sum(sum(col != '.' for col in row) for row in grid)

ans = 0
seen = set()
waiting = set([(0, 0)])
waiting_color = grid[0][0]

while len(seen) < tracks:
    ans += 1
    Q = deque(waiting)
    waiting.clear()

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

        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:
                if grid[nr][nc] == waiting_color:
                    Q.append((nr, nc))
                elif grid[nr][nc] == invert(waiting_color):
                    waiting.add((nr, nc))

    waiting_color = invert(waiting_color)

print(ans)

• Subtask 1: 8.333333333333334 / 30
• Subtask 2: 15.3125 / 70