### PROBLEM LINK:

**Author:** admin5

**Editorialist:** admin5

### DIFFICULTY:

MEDIUM

### PREREQUISITES:

Graph, Network Flow

### PROBLEM:

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 .

### DETAILED EXPLANATION:

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.