Submission #636387

#	Time	Username	Problem	Language	Result	Execution time	Memory
636387		Hello1234	Tracks in the Snow (BOI13_tracks)	Pypy 3	8.75 / 100	2098 ms	341528 KiB

tracks

import sys
from collections import deque
# sys.stdin = open('input.txt', 'r')
input = sys.stdin.readline

h, w = map(int, input().split())
empty, fox, rabbit = 0, 1, 2
mapping = {'.': empty, 'F': fox, 'R': rabbit}

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

# add padding!
grid.append([0]*len(grid[0]))
for row in grid:
    row.append(0)

queue = deque([(0, 0)])
curr_color = grid[0][0]
grid[0][0] = 0
color_cnt = 1
other_color_cnt = 0
ans = 0

while queue:
    i, j = queue.popleft()

    # if not grid[i][j]:  # already visited
    #     continue

    # curr_color = grid[i][j]
    # grid[i][j] = 0  # mark visited

    for ni, nj in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):
        if grid[ni][nj]:
            if grid[ni][nj] == curr_color:
                queue.appendleft((ni, nj))
                color_cnt += 1
            else:
                queue.append((ni, nj))
                other_color_cnt += 1
            grid[ni][nj] = 0

    color_cnt -= 1
    # print(color_cnt)
    # when we run out of the current color in the bfs queue (or when it 0/1 bfs switches from 0 to 1)
    if not color_cnt:
        color_cnt = other_color_cnt
        other_color_cnt = 0
        curr_color = not (curr_color-1) + 1  # switch the color
        ans += 1

print(ans)

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