Alice has challenegd Bob game of N puzzle.N puzzle is played on N*N grid with each cell containing distinct numbered tile from 1 to N*N-1 Except one which is empty cell and represented as 0.
Move Type 1 : Bob can pull out any tile he want and put it into any cell of his choice (not necessarily blank)
Move Type 2 : He can choose any tile and move it to any adjacent cell in 4 direcions regardless of weather cell is empty or not.
Goal to be achieved : Goal is to reach configuration where first row contains tiles 0,1,2..N-1 second row contains N,N + 1,N + 2..2*N-1 and last row contains N*(N-1)...N*N-1
Now we need to help Bob in finding how much extra work he will have to do if he chooses Move Type 2 which means if given position can be solved optimally using Move Type 1 in X moves and using Move Type 2 in Y moves then we need to find (Y-X) extra work.
Example : Let M=N*N=4 and initial configuration be
0 2 3 1
Here answer will be 1
Explanation : Using Type 1 move Bob can put out tiles 1,2,3 and put them in reuired order this takes him X=3 moves
Using Type 2 move he can move tile 1 UP,tile 2 DOWN and then LEFT and then tile 3 RIGHT to reach final goal.So Y=4