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()
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
43 ms |
6336 KB |
Execution failed because the return code was nonzero |
| 2 |
Correct |
23 ms |
3376 KB |
Output is correct |
| 3 |
Correct |
23 ms |
3492 KB |
Output is correct |
| 4 |
Runtime error |
77 ms |
6956 KB |
Execution failed because the return code was nonzero |
| 5 |
Correct |
84 ms |
6080 KB |
Output is correct |
| 6 |
Correct |
16 ms |
3284 KB |
Output is correct |
| 7 |
Correct |
24 ms |
3432 KB |
Output is correct |
| 8 |
Runtime error |
20 ms |
3504 KB |
Execution failed because the return code was nonzero |
| 9 |
Correct |
21 ms |
3668 KB |
Output is correct |
| 10 |
Correct |
103 ms |
7280 KB |
Output is correct |
| 11 |
Correct |
154 ms |
7584 KB |
Output is correct |
| 12 |
Runtime error |
73 ms |
5736 KB |
Execution failed because the return code was nonzero |
| 13 |
Correct |
88 ms |
6068 KB |
Output is correct |
| 14 |
Correct |
82 ms |
6000 KB |
Output is correct |
| 15 |
Correct |
687 ms |
35068 KB |
Output is correct |
| 16 |
Runtime error |
42 ms |
6336 KB |
Execution failed because the return code was nonzero |
| 17 |
Runtime error |
274 ms |
13740 KB |
Execution failed because the return code was nonzero |
| 18 |
Runtime error |
68 ms |
6988 KB |
Execution failed because the return code was nonzero |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
4196 KB |
Output isn't correct |
| 2 |
Execution timed out |
2091 ms |
89752 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2045 ms |
215124 KB |
Time limit exceeded |
| 4 |
Runtime error |
1685 ms |
100860 KB |
Execution failed because the return code was nonzero |
| 5 |
Execution timed out |
2078 ms |
171196 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2043 ms |
211964 KB |
Time limit exceeded |
| 7 |
Runtime error |
27 ms |
4236 KB |
Execution failed because the return code was nonzero |
| 8 |
Incorrect |
31 ms |
4136 KB |
Output isn't correct |
| 9 |
Incorrect |
22 ms |
3840 KB |
Output isn't correct |
| 10 |
Incorrect |
18 ms |
3660 KB |
Output isn't correct |
| 11 |
Incorrect |
26 ms |
4244 KB |
Output isn't correct |
| 12 |
Correct |
58 ms |
5568 KB |
Output is correct |
| 13 |
Execution timed out |
2089 ms |
87368 KB |
Time limit exceeded |
| 14 |
Runtime error |
1492 ms |
74616 KB |
Execution failed because the return code was nonzero |
| 15 |
Correct |
1055 ms |
53016 KB |
Output is correct |
| 16 |
Incorrect |
77 ms |
10640 KB |
Output isn't correct |
| 17 |
Runtime error |
267 ms |
40464 KB |
Execution failed because the return code was nonzero |
| 18 |
Execution timed out |
2076 ms |
118688 KB |
Time limit exceeded |
| 19 |
Runtime error |
1721 ms |
100804 KB |
Execution failed because the return code was nonzero |
| 20 |
Incorrect |
259 ms |
36668 KB |
Output isn't correct |
| 21 |
Execution timed out |
2086 ms |
160252 KB |
Time limit exceeded |
| 22 |
Execution timed out |
2064 ms |
167380 KB |
Time limit exceeded |
| 23 |
Execution timed out |
2060 ms |
138900 KB |
Time limit exceeded |
| 24 |
Runtime error |
526 ms |
92348 KB |
Execution failed because the return code was nonzero |
| 25 |
Execution timed out |
2041 ms |
209116 KB |
Time limit exceeded |
| 26 |
Execution timed out |
2055 ms |
189212 KB |
Time limit exceeded |
| 27 |
Execution timed out |
2037 ms |
208528 KB |
Time limit exceeded |
| 28 |
Execution timed out |
2064 ms |
200828 KB |
Time limit exceeded |
| 29 |
Execution timed out |
2048 ms |
199676 KB |
Time limit exceeded |
| 30 |
Execution timed out |
2087 ms |
204244 KB |
Time limit exceeded |
| 31 |
Runtime error |
664 ms |
93200 KB |
Execution failed because the return code was nonzero |
| 32 |
Execution timed out |
2067 ms |
197340 KB |
Time limit exceeded |
