>>107272849
>>107272828
>>107272797
wow got it thanks! yaaaa turns out I was trying get the "best" solution instead of the "greedy" and storing big sets of visited. reading is hard. :(
grid = [[int(x) for x in list(y)] for y in data.strip().splitlines()]
h, w = len(grid), len(grid[0])
def dfs(y, x, g):
q = [(g[y][x], y, x)]
g[y][x] = 0
while q:
s, y, x = q.pop()
for ny, nx in ((y+1,x), (y-1,x), (y,x+1), (y,x-1)):
if not (0 <= ny < h and 0 <= nx < w):
continue
if not g[ny][nx]: # visited
continue
if s >= g[ny][nx]: # can move to <= height
q.append((g[ny][nx], ny, nx))
g[ny][nx] = 0 # mark visited
best = set()
for i in range(3):
res = (0,0,0)
copy = [row[:] for row in grid]
for y,x in best:
bfs(y, x, copy)
for y in range(h):
for x in range(w):
if (y,x) in best:
continue
if copy[y][x] < 3:
continue
test = [row[:] for row in copy]
dfs(y, x, test)
total = sum(1 for row in test for x in row if x == 0)
if total > res[0]:
res = (total, y, x)
best.add((res[1],res[2]))
print(best)
print(res)
