Search code examples
algorithmsearchpath-finding

Find minimum number of blockage needed to prevent A from reaching B

You are given a 2D array representing a map e.g.:

A . X .

. . . .

X X . B

Note: '.' represents traversable positions 'X' represents non-traversable positions

THE QUESTION:

Find the minimum number of blockage you can add to prevent A from reaching B.

For the above example, the answer is 1 from a positioning like this:

A . X .

. . % .

X X . B

Note: '%' represents the inserted blockage

MY ATTEMPT:

I tried to solve this with a simple DFS thrown to 4 different direction and only increment total blockage number when that specific path leads to B. However this creates problem in marking paths already traversed as marking suboptimal paths arbitrarily might block search effort of other directions.

Any pointers on how to solve this optimally? Or is there any similar coding problems in the same vein as the above problem at Leetcode/Codeforces/etc.?

EDIT 1: According to the answer of Jacob Steinebronn, this problem can be solved with a Max Flow Algorithm. So after some time trying to understand the algorithm, this is my new attempt:

  1. Construct a directed graph from the 2d map provided. I assume every vertices will be connected to each other with single direction edges pointing away from the Start node. I assume the resulting graph should be acyclic?
  2. Initialize every edges' capacity with 1 (?) as I don't want the algorithm to go through the same path more than once.
  3. Run Max Flow algorithm (Ford-Fulkerson, Dinic, or Karp-Edmond) on that graph and the Max flow is the minimum cut needed to prevent A from reaching B.

Am I on the right track?

Solution

  • This problem is a classic example of the identity that Min Cut = Max Flow. Let's break this down: The question can be generalized: Given a graph, and a start and and end, what is the Min number of edges to Cut such that there is no path from start to end. This can be solved by an algorithm called Max Flow. Thus, to solve this problem, construct a graph where each node is connected to all of the non-blocked cells adjacent to it (note directed or non-directed edges) and run Max Flow to get your result.