Submission #346479

#TimeUsernameProblemLanguageResultExecution timeMemory
346479IshanP15Tracks in the Snow (BOI13_tracks)Cpython 3
36.98 / 100
2100 ms147200 KiB
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)]
    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[0]) 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)
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...