oj.uz

Submission #716241

# Submission time Handle Problem Language Result Execution time Memory
716241 2023-03-29T11:08:50 Z ateacode Tracks in the Snow (BOI13_tracks) Python 3
51.875 / 100
 2000 ms 207964 KB 
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: 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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 942 ms 34652 KB Output is correct
2 Correct 16 ms 3364 KB Output is correct
3 Correct 21 ms 3484 KB Output is correct
4 Correct 596 ms 21316 KB Output is correct
5 Correct 82 ms 6052 KB Output is correct
6 Correct 17 ms 3368 KB Output is correct
7 Correct 20 ms 3508 KB Output is correct
8 Correct 31 ms 3912 KB Output is correct
9 Correct 22 ms 3544 KB Output is correct
10 Correct 121 ms 7208 KB Output is correct
11 Correct 151 ms 7604 KB Output is correct
12 Correct 302 ms 12320 KB Output is correct
13 Correct 98 ms 5984 KB Output is correct
14 Correct 84 ms 6024 KB Output is correct
15 Correct 673 ms 34712 KB Output is correct
16 Correct 896 ms 34580 KB Output is correct
17 Correct 403 ms 20072 KB Output is correct
18 Correct 556 ms 21280 KB Output is correct

Subtask #2
21.875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 6004 KB Output is correct
2 Execution timed out 2074 ms 87508 KB Time limit exceeded
3 Execution timed out 2100 ms 201368 KB Time limit exceeded
4 Execution timed out 2041 ms 102316 KB Time limit exceeded
5 Execution timed out 2072 ms 159360 KB Time limit exceeded
6 Execution timed out 2084 ms 202568 KB Time limit exceeded
7 Correct 63 ms 6116 KB Output is correct
8 Correct 66 ms 6080 KB Output is correct
9 Correct 118 ms 7644 KB Output is correct
10 Correct 45 ms 4912 KB Output is correct
11 Correct 56 ms 5292 KB Output is correct
12 Correct 53 ms 5456 KB Output is correct
13 Execution timed out 2090 ms 87740 KB Time limit exceeded
14 Correct 1491 ms 73440 KB Output is correct
15 Correct 1051 ms 52012 KB Output is correct
16 Correct 1368 ms 71128 KB Output is correct
17 Execution timed out 2085 ms 99860 KB Time limit exceeded
18 Execution timed out 2079 ms 113816 KB Time limit exceeded
19 Execution timed out 2062 ms 104904 KB Time limit exceeded
20 Execution timed out 2055 ms 110352 KB Time limit exceeded
21 Execution timed out 2091 ms 155944 KB Time limit exceeded
22 Execution timed out 2093 ms 163620 KB Time limit exceeded
23 Execution timed out 2081 ms 131304 KB Time limit exceeded
24 Execution timed out 2071 ms 155752 KB Time limit exceeded
25 Execution timed out 2081 ms 202000 KB Time limit exceeded
26 Execution timed out 2087 ms 176328 KB Time limit exceeded
27 Execution timed out 2091 ms 207964 KB Time limit exceeded
28 Execution timed out 2067 ms 198280 KB Time limit exceeded
29 Execution timed out 2075 ms 195464 KB Time limit exceeded
30 Execution timed out 2094 ms 201740 KB Time limit exceeded
31 Execution timed out 2079 ms 148768 KB Time limit exceeded
32 Execution timed out 2085 ms 193520 KB Time limit exceeded