Submission #1235054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235054		jiayiiyaij	Tracks in the Snow (BOI13_tracks)	Pypy 3	31.04 / 100	2136 ms	1114112 KiB

tracks

import sys

H, W = map(int, sys.stdin.readline().split())
mapp = [list(sys.stdin.readline()) for _ in range(H)]

if mapp[0][0] == 'R':
    ani = ['R', 'F']
else:
    ani = ['F', 'R']

dirs = [(0,1), (1,0), (0,-1), (-1,0)]
count = 0
while True:
    for a in ani: # Loops between the two types of animals
        flag = 0 # Checks if animal is detected
        vis = [[-1]*W for _ in range(H)]
        vis[0][0] = 1
        queue = [(0,0)]
        # BFS
        for r, c in queue:
            for x, y in dirs:
                rr = r+x
                cc = c+y
                if rr < 0 or rr >= H or cc < 0 or cc >= W:
                    continue
                if vis[rr][cc] == 1:
                    continue
                
                if mapp[rr][cc] == a:
                    flag = 1
                if mapp[rr][cc] == a or mapp[rr][cc] == '#':
                    vis[rr][cc] = 1
                    mapp[rr][cc] = '#'
                    queue.append((rr, cc))
        if flag == 0:
            break
        count += 1
    if flag == 0:
        break

print(count)

Compilation message (stdout)

Compiling 'tracks.py'...

=======
  adding: __main__.pyc (deflated 38%)

=======

• Subtask 1: 26.6667 / 30
• Subtask 2: 4.375 / 70