Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Tour in Grid

Limits: 5s, 1.0 GB

You have a grid with n rows and m columns. Cell at the ith row and the jth column is called Cell(i, j) and id of the cell is G­i,j. Each cell has a unique id from 1 to n*m. You can jump from Cell(i,j) to Cell(x,y) by consuming power {(i-x)2+(j-y)2}*(Gx,y-Gi,j). In each day, you are going to select a number D. In that day, you can jump D cells, meaning if you are currently in a cell with id number p, then in one jump, you can go to another cell which id is (p+D). In the second jump you will be in (p+2*D), then (p+3*D) and so on. At kth day, you have to go from pth cell to qth cell. You can select different D for each day. Now, you want to minimize the total power consumption.


Input starts with two integers n and m.

Each of the next n lines contain m integers representing the grid.

Then the next line contains one integer Q, representing the number of days.

The next Q lines will have the information of each day. In each line, there will be two id p and q.  


1 ≤ n, m ≤ 300

1 ≤ Q ≤ 105

1 ≤ p ≤ q ≤ n*m


For each day, you have to output minimum power on a line by itself.


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


In the last day, you want to go from 1st cell to 9th. You can select 1,2,4,8 as the candidate values for D for that day. Otherwise you can not go from 1st cell to 9th cell.

If you select 1 as D, you have to go through 1,2,3,4,5,6,7,8,9. The cost will be {(1-2)2+(1-1)2}*(2-1)+ {(2-1)2+(1-3)2}*(3-2)+ {(1-1)2+(3-2)2}*(4-3)+ {(1-2)2+(2-2)2}*(5-4)+ {(2-3)2+(2-3)2}*(6-5)+ {(3-2)2+(3-3)2}*(7-6)+ {(2-3)2+(3-1)2}*(8-7)+ {(3-3)2+(1-2)2}*(9-8) = 17

If you select 2 as D, you have to go through 1,3,5,7,9. The cost will be {(1-1)2+(1-3)2}*(3-1)+ {(1-2)2+(3-2)2}*(5-3)+ {(2-2)2+(2-3)2}*(7-5)+ {(2-3)2+(3-2)2}*(9-7)=18.

If you select 4 as D, you have to go through 1,5,9. The cost will be {(1-2)2+(1-2)2}*(5-1)+ {(2-3)2+(2-2)2}*(9-5) =12.

If you select 8 as D, you have to go through 1,9. The cost will be {(1-3)2+(1-2)2}*(9-1) =40

So, the minimum cost will be 12.


Login to submit