Submission #646827

#	Time	Username	Problem	Language	Result	Execution time	Memory
646827		beaconmc	Tracks in the Snow (BOI13_tracks)	Pypy 3	49.69 / 100	2144 ms	1016396 KiB

tracks

from heapq import *
n,m = map(int, input().split())

grid = [list(input()) for i in range(n)]
visited = [[0 for i in range(m)]for i in range(n)]
depth = [[0 for i in range(m)]for i in range(n)]

ani = []
if grid[0][0]=="F":
    ani = ["F","R"]
else: ani = ["R","F"]


a = []
heappush(a,(0,0,0))

while len(a):
    node = heappop(a)
    if visited[node[1]][node[2]]:
        continue
    visited[node[1]][node[2]] = True
    depth[node[1]][node[2]] = node[0]

    for (i,j) in [(1,0),(-1,0),(0,-1),(0,1)]:
        x = node[1] + i
        y = node[2] + j

        if 0<=x<n and 0<=y<m and grid[x][y] != ".":
            if grid[x][y] == ani[node[0]%2] and not visited[x][y]:
                heappush(a, (node[0], x,y))

            if grid[x][y] != ani[node[0]%2] and not visited[x][y]:
                heappush(a, (node[0]+1, x,y))
maxi = -1

for i in depth:
    maxi = max(maxi, max(i))
print(maxi+1)

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