TC SRM360 D1 500 (PrinceOfPersia)

The problem statement can be accessed via:
http://www.topcoder.com/stat?c=problem_statement&pm=7876&rd=10772

This problem lends itself to a graph problem as can be observed by the fact that, the input format is in a grid format and there are obstacles (forbidden cells) and its related to path accessibility between the prince and princess. One way to solve this problem is to use the Maximum Flow algorithm. Take note, although they are required to "meet" in any cell - it is sufficient enough for the prince (or princess) to go to princess (or prince) as it is not limited by time.

How does it relate to the Maximum Flow problem? We are basically asked to find the minimum cut and using the max-flow min-cut theorem we can calculate this by running a maximum flow algorithm through the graph. To see that what we really want is the minimum cut, let's revise the definition of a cut (in terms of graph theory of course): A cut is a partition of vertices of a graph into two disjoint subsets. So if we imagine the princess in one subset and the prince in another subset, the minimum cut between these two disjoint subsets is the number of accessible ways in which one can go to another.

So now we move on to applying the actual algorithm to the problem. If we let each empty cell be a node (or vertex) on the network and assign 1-capacity edges to adjacent empty nodes and apply flow from one "P" (source) to another "P" (sink) do we obtain the correct answer? Well, unfortunately no. The problem lies in which one "bottleneck" node (on the minimum cut set) can have an outgoing flow of more than 1, so it may over-calculate the answer. To see this, consider the example:

# . P
. . .
P . #

The central node in the snippet can have an incoming flow of 2 if both its adjacent nodes gives it a flow of 1. The problem with this is that the bottom-left P (assume it to be the sink) will have a maximum flow of 2 (and hence a minimum cut of 2). So our problem now is to ensure that each empty node will only give out a maximum of 1 out-going flow.

One wrong approach is to ensure that there is only an incoming flow of maximum 1 (i.e. 1 edge going into the node). The problem with this is that it totally breaks down the network layout. The solution is to further break each empty cell into 2 nodes: let's call them A and B. These nodes are used as "filters" or more precisely input and output filters. The edge from A->B will have a capacity of 1 which limits the maximum flow across the node to be 1 whereas the incoming and outgoing arcs of A and B respectively are infinite. This allows the network to retain the correct layout (and hence the correct answer) as well as fixing the original problem. We just need to ensure that all input arcs to the node use the sub-node A, and all output arcs from the node use the sub-node B.

Implementation-wise it's pretty standard if you follow the ideas discussed earlier. A sample implementation from the practice room is given below:

// the maximum number of vertices
#define NN 256

// adjacency matrix (fill this up)
int cap[NN][NN];

// flow network
int fnet[NN][NN];

// BFS
int q[NN], qf, qb, prev[NN];

int fordFulkerson( int n, int s, int t )
{
    memset( fnet, 0, sizeof( fnet ) );
    int flow = 0;
 // find an augmenting path of at least 1
    while( true )
    {
        memset( prev, -1, sizeof( prev ) );
        qf = qb = 0;
        prev[q[qb++] = s] = -2;
        while( qb > qf && prev[t] == -1 )
            for( int u = q[qf++], v = 0; v < n; v++ )
                if( prev[v] == -1 && fnet[u][v] - fnet[v][u] < cap[u][v] )
                    prev[q[qb++] = v] = u;
        if( prev[t] == -1 ) break;
        // get the bottleneck capacity
        int bot = 0x7FFFFFFF;
        for( int v = t, u = prev[v]; u >= 0; v = u, u = prev[v] )
            bot <?= cap[u][v] - fnet[u][v] + fnet[v][u];
        // update the flow network
        for( int v = t, u = prev[v]; u >= 0; v = u, u = prev[v] )
            fnet[u][v] += bot;
        flow += bot;
    }
    return flow;
}

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

#define INF 999999

int PrinceOfPersia::minObstacles(vector <string> maze) {
 int res = 0;
 bool gotP = false;
 int source = 0, sink = 0;
 for (int i = 0; i < maze.size(); i++) {
  for (int j = 0; j < maze[i].size(); j++) {
      // assign the source and sink
   if (maze[i][j] == 'P' && !gotP) { 
     source = (i * maze[0].size() + j)*2; gotP = true; 
   }
   else if (maze[i][j] == 'P' && gotP) { 
     sink = (i * maze[0].size() + j)*2; 
   }
   // build connections
   if (maze[i][j] == '.') { 
     cap[(i * maze[0].size() + j)*2][(i * maze[0].size() + j)*2+1] = 1; 
   }
   else if (maze[i][j] == 'P') { 
     cap[(i * maze[0].size() + j)*2][(i * maze[0].size() + j)*2+1] = INF; 
   }
   // iterate through adjacent cells
   for (int k = 0; k < 4; k++) {
    int mi = i + dx[k];
    int mj = j + dy[k];
    if (mi < 0 || mj < 0 || mi >= maze.size() || mj >= maze[0].size()) 
      continue;
    // impossible case
    if (maze[mi][mj] == 'P' && maze[i][j] == 'P') return -1;
    if (maze[mi][mj] != '#') { 
     cap[(i * maze[0].size() + j)*2+1][(mi * maze[0].size() + mj)*2] = INF;
    }
   }
  }
 }
 int flow = fordFulkerson(maze[0].size()*maze.size()*2, source, sink);
 return res = flow;
}