Submission #716236

#	Time	Username	Problem	Language	Result	Execution time	Memory
716236		ateacode	Tracks in the Snow (BOI13_tracks)	Cpython 3	22.71 / 100	2091 ms	215124 KiB

tracks

from collections import deque

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

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

  return valid_coords


def findMinPossibleAnimalsBfs(grid, w, h):
  '''
  When we model this problem as a graph problem (naturally because of the grid), we must think about what that gives us. What is an edge in this case? Well it depends, an edge between same animals just reveals a valid path one animal has taken. An edge between different animals represents a transition to another animal. i.e. atleast one more animal is needed.
  '''

  # We maintain the inv: when a node is visited, it's path required the smallest amount of transitions.

  # we enforce that the head of deque is always the shortest distance.
  toVisit = deque([(0, 0)])
  distances = {
    (0,0): 1
  }
  minAnimals = 1

  def isNotSymbolOrVisited(lol):
    lolx, loly = lol
    return grid[loly][lolx] != '.' and lol not in distances
  
  while len(toVisit) > 0:
    node = toVisit.popleft()
    x, y = node
    symbol = grid[y][x]
    for n in filter(isNotSymbolOrVisited, getNeighbours(w, h, node)):
      # go through each valid neighbour
    
      x1, y1 = n;
      if grid[y1][x1] == symbol:
        # we can continue to traverse with no cost. this must be shortest path to n 
        toVisit.appendleft(n)
        distances[n] = distances[node]
      else:
        toVisit.append(n)
        distances[n] = distances[node] + 1
        
  return max(distances.values())
        
  
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[0]][neighbour[1]]
        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(findMinPossibleAnimalsBfs(grid, w, h))

main()

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