제출 #715920

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
715920		ateacode	Tracks in the Snow (BOI13_tracks)	Cpython 3	0 / 100	2096 ms	193356 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 < 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 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: the min possible animals for a distance 'd' from origin is 'x'
  # we expand 'd' using bfs and take special care to only increment 'x' when necessary.

  toVisit = deque([(0, 0)])
  seen = set([(0, 0)])
  minAnimals = 0
  
  while len(toVisit) > 0:
    x, y = toVisit.popleft()
    symbol = grid[y][x]

    if (x - 1 >= 0 and grid[y][x-1] != symbol) and (y - 1 >= 0 and grid[y -1][x] != symbol):
      minAnimals += 1

    for n in getNeighbours(w, h, (x, y)):
      if n not in seen:
        toVisit.append(n)
        seen.add(n)
        
  return minAnimals    
        
  
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(findMinPossibleAnimalsBfs(grid, w, h))

main()

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