Programming assignment A4M33PAL

Task: The Puzzle

Consider a puzzle that is formed by a two-dimensional array M×N. Every cell in the puzzle contents one natural number in range from 1 to M·N. Every natural number in range from 1 to M·N is in the puzzle only once. The puzzle can be changed by the following four actions only:

  1. left shift of row
  2. right shift of row
  3. left shift of column
  4. right shift of column

The shift is defined in the following way: Let a0 to ak-1 are all cells of some selected row or column which we want to shift. The right shift permutes the cells according to their indices pR, where pR[i]=(i+1) mod k. The left shift permutes the cells according to their indices pL, where pL[i]=(i+k-1) mod k.

Your objective is to find out a minimal number of actions that change the puzzle from some defined starting state into some defined target state.

The Input

The first line contains two numbers M and N separated by space character. M and N define dimensions of the puzzle.

The other lines contain descriptions of two puzzles. The first puzzle is a starting state puzzle and the second is a target state puzzle.

Every puzzle is represented by M lines, where every line contains N natural numbers separated by space character.

You can assume that the input is every time correct and the maximal number of cells in the puzzle is less or equal to 20.

The Output

The output is always only one line with one number that represents the minimal number of actions needed to composition of the puzzle from the starting state into the target state. If the composition of the puzzle is not possible then the result number is -1.



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




For your convenience we add one possible composition of the puzzle in four steps.

The starting state puzzle:

1 2 3 4
5 6 7 8 

Left shift of the first row:

2 3 4 1
5 6 7 8 

Right shift of the second row:

2 3 4 1
8 5 6 7  

Left shift of the second column:

2 5 4 1
8 3 6 7  

Right shift of the third column:

2 5 6 1
8 3 4 7