CareerCup

This can be done in two phases.
1. In phase 1, find out the location of the grey cell by scanning the 2D array and let it's location be (i,j).
2. In phase 2, find out the paths from (0,0) to (i,j) and then from (i,j) to (N-1,N-1) using DP. The black cells can be treated as 'blocked' sites/paths and we have known DP solutions to traverse from a cell (i1, j1) to (i2,j2) with some paths blocked in between them.

We can use a modified version of A*, having the heuristic to take into account the manhattan distance to the grey cell if the cell has not gone there yet. in addition we need to know for each candidate the path, so that we do not pass on the same cell twice. Thr main problem here is the space complexity. How do we store the path for each candidate. It could generate a huge amount of data.

If the matrix were instead a graph, and we start at one vertex, must to through a gray vertex, and then finish at another vertex such that no edge is traveled twice, then we want to find two edge-disjoint paths from the gray vertex, one ending at the start location and the other ending at the end location. This can be solved with a network flow, where each edge has capacity 1, a flow of 2 starts at the gray vertex, and two flows of 1 are directed from the start and end to the sink. So a path is found iff the maximum flow is 2.

So it remains to transform the matrix into a graph. To do this, for each cell c, make two vertices c_in and c_out; direct an edge from c_in to c_out. Then, for each neighbor n, direct edges from c_out to n_in. This way, each path of the matrix must go through c_in and c_out for each cell in the path.

Time complexity with Ford-Fulkerson is O(N*M), since BFS is O(N*M) and max flow is only 2.