> algorithmically find the optimal solution for this kind of problem for much bigger grids.
Great, now I've been double nerd-sniped - once for the thing itself and another for 'What would an optimiser for this look like? Graph cuts? SAT/SMT? [AC]SP?'
I'd bet it's NP-hard. The standard reduction to a flow problem only tells you if a cut exists (by min-cut max-flow duality), but here we want the cut of size at most N that maximizes enclosed area.
The Leetcode version of this is "find articulation points", which is just a DFS, but it's less general than what is presented here.
Great, now I've been double nerd-sniped - once for the thing itself and another for 'What would an optimiser for this look like? Graph cuts? SAT/SMT? [AC]SP?'