title: How to detect squares on a grid which can NEVER be part of a shortest path after adding blocks?
body: <p>I have a grid with a start, finish, and some walls.  Units take the shortest path <em>(moving only up/down/left/right)</em> from the start to the finish, without passing through walls.</p>
  
  <p><img src="https://i.stack.imgur.com/jtiXQ.png" alt="shortest path"></p>
  
  <p>The user is allowed to add as many extra walls as they want to change the path.</p>
  
  <p><img src="https://i.stack.imgur.com/YzfEc.png" alt="adding walls"></p>
  
  <p>However, notice that no matter how many walls are added or where they're added, there are some squares that can <strong>never</strong> be part of the shortest path!</p>
  
  <p><img src="https://i.stack.imgur.com/mo6iP.png" alt="These squares can never be part of the shortest path!"><br>
  <em>These squares can never be part of the shortest path!</em></p>
  
  <p>I'm looking for a way to detect which squares can never be part of the shortest path.</p>
  
  <hr>
  
  <p>The above cases are easy enough to find; but there are more complex cases.  Consider:</p>
  
  <p><img src="https://i.stack.imgur.com/RdCxV.png" alt="None of the squares with red-dots can ever be part of the best-path"></p>
  
  <p>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.</p>
  
  <p>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?</p>