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()
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2062 ms |
38712 KB |
Time limit exceeded |
| 2 |
Correct |
61 ms |
3020 KB |
Output is correct |
| 3 |
Correct |
84 ms |
3192 KB |
Output is correct |
| 4 |
Correct |
1842 ms |
42432 KB |
Output is correct |
| 5 |
Execution timed out |
2061 ms |
8080 KB |
Time limit exceeded |
| 6 |
Correct |
58 ms |
2960 KB |
Output is correct |
| 7 |
Correct |
92 ms |
3208 KB |
Output is correct |
| 8 |
Correct |
73 ms |
4008 KB |
Output is correct |
| 9 |
Correct |
137 ms |
3528 KB |
Output is correct |
| 10 |
Execution timed out |
2088 ms |
11936 KB |
Time limit exceeded |
| 11 |
Correct |
381 ms |
19296 KB |
Output is correct |
| 12 |
Execution timed out |
2072 ms |
20552 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2066 ms |
7992 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2082 ms |
8036 KB |
Time limit exceeded |
| 15 |
Execution timed out |
2065 ms |
37112 KB |
Time limit exceeded |
| 16 |
Execution timed out |
2076 ms |
38572 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2080 ms |
22348 KB |
Time limit exceeded |
| 18 |
Correct |
1946 ms |
42260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2067 ms |
5172 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2079 ms |
36260 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2106 ms |
137060 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2061 ms |
52248 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2036 ms |
82500 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2108 ms |
205704 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2071 ms |
5164 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2073 ms |
5104 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2068 ms |
12800 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2075 ms |
4468 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2063 ms |
5132 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2087 ms |
3704 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2036 ms |
35992 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2081 ms |
28172 KB |
Time limit exceeded |
| 15 |
Execution timed out |
2066 ms |
12928 KB |
Time limit exceeded |
| 16 |
Execution timed out |
2070 ms |
24612 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2045 ms |
56668 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2037 ms |
36456 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2054 ms |
52400 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2053 ms |
33412 KB |
Time limit exceeded |
| 21 |
Execution timed out |
2009 ms |
85136 KB |
Time limit exceeded |
| 22 |
Execution timed out |
2096 ms |
82500 KB |
Time limit exceeded |
| 23 |
Execution timed out |
2080 ms |
93692 KB |
Time limit exceeded |
| 24 |
Execution timed out |
2088 ms |
85520 KB |
Time limit exceeded |
| 25 |
Execution timed out |
2024 ms |
135972 KB |
Time limit exceeded |
| 26 |
Execution timed out |
2057 ms |
218268 KB |
Time limit exceeded |
| 27 |
Execution timed out |
2080 ms |
246404 KB |
Time limit exceeded |
| 28 |
Execution timed out |
2084 ms |
207692 KB |
Time limit exceeded |
| 29 |
Execution timed out |
2080 ms |
201612 KB |
Time limit exceeded |
| 30 |
Execution timed out |
2073 ms |
238696 KB |
Time limit exceeded |
| 31 |
Execution timed out |
2088 ms |
149592 KB |
Time limit exceeded |
| 32 |
Execution timed out |
2091 ms |
241300 KB |
Time limit exceeded |
