Graph, Network Flow
You are given a grid of N X M, each cell of grid contain a number from 1 to 9, you are asked to find out the number of sequence which start from 1 and end with 9 and all numbers should be connected sequentially like 1 is directly connected to 2 and 2 is directly connected to 3 and so on.
Each block of grid can be directly connected with it’s UP , DOWN ,LEFT, RIGHT blocks .
You are given a N X M grid and each cell contain value from 1 to 9. In order to solve this problem you can use the concept of network flow. According to flow concept we need two more nodes source S and sink T , then we can connect each cells of grid which contain 1 to source with flow capacity of 1 because we can use each block once . And connect all cells of grid which contain 9 to sink with flow capacity of 1. And connect all intermediate node they have difference of their cell value is 1 with flow capacity of 1 like we can connect 1 with all 2’s and all 2’s with all 3’s with flow capacity of 1 and so on. Once the flow network is ready , you can apply any maximum flow algorithm to find out maximum flow of network.
Time complexity of this approach is O(N*E^2) , where E is edges in network.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.