Submission #715768

#	Time	Username	Problem	Language	Result	Execution time	Memory
715768		ateacode	Tracks in the Snow (BOI13_tracks)	Cpython 3	15 / 100	2108 ms	246404 KiB

tracks

def getNeighbours(w, h, coord):
  x, y = coord
  valid_coords = []

  if x > 0:
    valid_coords.append((x-1, y))
  if x < w - 1:
    valid_coords.append((x + 1, y))
  if y > 0:
    valid_coords.append((x, y - 1))
  if y < h - 1:
    valid_coords.append((x, y + 1))

  return valid_coords

def findMinPossibleAnimals(grid, w, h):
  '''
  have a 'allowed' character, and a visited coord set. You run bfs such that you can visit a character if they are a allowed character or in the visited coord set. otherwise, they must be a new character which must be saved for the next pass.
  '''

  allowed_char = grid[0][0]
  visited_chars = set()


  i = 0

  '''
  inv: there is atleast one unexplored char in grid equal to allowed_char
  '''
  while allowed_char != None:
    i += 1
    next_char = None
    visited = { (0, 0) }
    toVisit = [(0, 0)]
    while len(toVisit) > 0:
      node = toVisit.pop()
      for neighbour in getNeighbours(w, h, node):
        symbol = grid[neighbour[1]][neighbour[0]]
        if symbol == '.' or neighbour in visited:
          continue
        if neighbour in visited_chars or symbol == allowed_char:
          visited.add(neighbour)
          toVisit.append(neighbour)
        else:
          next_char = symbol

    visited_chars.update(visited)
    allowed_char = next_char

  return i

def parseGrid(h, w):
  grid = []
  for row in range(h):
    row_inp = [c for c in input()]
    grid.append(row_inp)
  return grid

def main():
  h, w = [int(s) for s in input().split()]
  grid = parseGrid(h, w)

  print(findMinPossibleAnimals(grid, w, h))

main()

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