PESTS - Editorial



Author: admin5
Editorialist: admin5




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 solution can be found here.

For clarification, how many pests are there in:

1 2 3 4
5 9 4 5
9 8 7 6

1? 2? 4? The way you’re solving it suggests that there is only meant to be one here.

yeah exactly!!

Is maxflow solution actually correct??

Yeah, in above test case there is only one pest according to problem statement.