Algorithm to enclose a 2D-gridbased-room efficient

Question

I have the problem that I have a grid-based room which has 1 or more exits and I want to "secure" the room with minimal effort.

Here a little Example:

In this example black squares are not passable, white ones are and the ones with the arrows are the exits that should not be able to be reached.

I wan't to enclose the yellow square by converting white squares into black ones. I want to use as few conversions as possible.

Two ideas I found until now:

1 The fastest algorithm in my opinion would be to just convert all squares around the exits but it would not be the most efficient algorithm since in this example it would cost 9 conversions (13 if diagonal movement is possible) but its possible to enclose the yellow block with only 3 (5) conversions.

2 I found the Flood fill Algorithm, which would enable me to check if the area around the yellow square is enclosed but I can't think of a (cpu-)efficient method to try out possible conversions until I find the solution with the least conversions needed.

The Method should be able to enclose more then one targets, since otherwise an optimal solution would be often to just enclose the yellow block with 9 conversions around him. Therefore I added to my picture the green block, so the algorithm should be able to enclose all targets.

If you don't have an idea how to solve it but a hint where I could look into to find a possible solution I would be happy to hear it!

Thanks, Niko

Answer 1

This is a graph cut problem.

Build a graph with one vertex per square. Add an edge between each pair of adjacent vertices (i.e., where you can go from one to the other in a single step). Add an extra "source" vertex $s$, and an edge from $s$ to each starting point (yellow/green block). Add an extra "sink" vertex $t$, and an edge from each exit to $t$.

Now your mission is to find a minimum vertex cut that separates $s$ from $t$, i.e., a subset $S$ of vertices such that every path from $s$ to $t$ traverses at least one vertex of $S$. There are standard algorithms for the minimum vertex cut problem, which you can find by searching the literature.

See also https://en.wikipedia.org/wiki/Vertex_separator and https://cstheory.stackexchange.com/q/2877/5038 and https://cstheory.stackexchange.com/q/29464/5038.

You'll need to add the extra constraint that the subset $S$ cannot include $s$ nor $t$, but I expect it should be easy to incorporate this constraint into standard algorithms for vertex cut.