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!