Submission #346478

#	Time	Username	Problem	Language	Result	Execution time	Memory
346478		IshanP15	Tracks in the Snow (BOI13_tracks)	Cpython 3	1.67 / 100	2107 ms	149140 KiB

tracks

from queue import Queue
H,W = map(int, input().split())

grid = []
for i in range(H):
    inp = input()
    row = [char for char in inp]
    grid.append(row)

def adjs(loc):
    x,y = loc[0], loc[1]
    possibleAdjs = [(x+1,y), (x-1,y), (x,y+1), (x,y-1), (x-1,y-1), (x+1,y+1), (x-1,y+1), (x+1, y-1)]
    return [adj for adj in possibleAdjs if validAdj(adj)]
def validAdj(adj):
    x,y = adj[0],adj[1]
    return x < len(grid) and y < len(grid) and x > -1 and y > -1
def BFS(animal):
    newQueue = Queue()
    while not Q.empty():
        nextLoc = Q.get()
        neighbors = adjs(nextLoc)
        for neighbor in neighbors:
            if neighbor not in visited and grid[neighbor[0]][neighbor[1]] != '.':
                if grid[neighbor[0]][neighbor[1]] != animal:
                    newQueue.put(neighbor)
                else:
                    Q.put(neighbor)
                visited.add(neighbor)

    return newQueue

start = (0,0)
visited = set()
visited.add(start)
Q = Queue()
Q.put(start)

currAnimal = grid[0][0]
numAnimals = 0
while( not Q.empty()):
    Q = BFS(currAnimal)
    numAnimals += 1
    if currAnimal == 'F':
        currAnimal = 'R'
    else:
        currAnimal = 'F'
print(numAnimals)

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