How to detect squares on a grid which can NEVER be part of a shortest path after adding blocks?

Question

I have a grid with a start, finish, and some walls. Units take the shortest path (moving only up/down/left/right) from the start to the finish, without passing through walls.

The user is allowed to add as many extra walls as they want to change the path.

However, notice that no matter how many walls are added or where they're added, there are some squares that can never be part of the shortest path!

These squares can never be part of the shortest path!

I'm looking for a way to detect which squares can never be part of the shortest path.

---

The above cases are easy enough to find; but there are more complex cases. Consider:

In the above image, none of the squares with red dots can ever be part of the best path, because there's only one entrance to that area, and it's only two spaces wide. If it were three spaces wide, or if any one of the walls were removed, most of those squares could potentially be part of the best path.

I've been trying to figure out a way to detect cases like the above (mostly using min-cuts and flood-fills), but without success. Does anyone know of a way to solve this problem?

Answer 1

Consider any path from S to F. That path could be a shortest path (if you delete every other square) unless you can take "shortcuts" using only those tiles. This only happens when you have two adjacent squares that aren't adjacent in the path. So you need to consider all pairs of adjacent squares; anything they disconnect from S or F (without disconnecting S from F) can't be part of a shortest path. Also, tiles that can be disconnected by a single square can't be part of any path (that doesn't repeat vertices) from S to F, so they need to go too.

Let N be the number of squares in the grid. For any particular pair of squares (there are O(N) of them), what gets disconnected can be computed in O(N) time with a floodfill, so this is O(N^2). Which is cheaper than min-cut, which you mentioned trying, so I assume its cheap enough for you.