Consider a grid with N rows and M column. Let (i, j) represent a cell at ith row and jth column. we have a matrix 'cost' where cost[i][j] represent cost of visiting cell (i, j) in a grid. cost[i]][j] is always a positive integer.
K people are planning to take a trip from cell (xi, yi) to (pi, qi) for all 1 <= i <= K. Each person can move only to cell which is edge adjacent to his current cell. All K people start moving at same time simultaneously from their starting cell and stop when they reach to their destination. No one can stop in his journey before reaching destination.No two person can be in same cell at any instant of time.
The total cost of journey of one person is sum of cost of each cell that he visit in his trip from (xi, yi) to (pi, qi) inclusive. Our goal is to minimize the sum of total cost of trip of each of K person, or find it is not possible for all K person to complete trip.
The only constraint that makes this problem hard is that there cannot be more than one person in a cell at any instant. Without it its a normal dp problem.
Please Suggest an algorithm with best possible time and space complexity for this problem.One may also assume that N, M, K not going to be more than 30