Problem Description

You are given a slide puzzle board of dimensions $H$ rows and $W$ columns, as shown in Figure 1.

Figure 1. Slide Puzzle Board

Each cell is assigned a unique number from $1$ to $H \times W - 1$, and one cell is left empty.

In this slide puzzle, you are allowed to swap the empty cell with one of its adjacent cells (left, right, up, or down). However, a swap is not allowed if there is no cell in the desired direction.

You want to reach the completed state by performing any number of swap operations. The completed state is defined as having the numbers sequentially numbered from the top-left to the bottom-right, with the empty cell at the bottom-right (Figure 2).

Figure 2. Completed Board

Specifically, the completed board is:

• Cell numbered $i\ (1 \leq i \leq H \times W - 1)$ is located at $(1 + [(i-1) \div W], 1 + (i-1) \% W)$
• The empty cell is at $(H, W)$

where $[a \div b]$ denotes the integer part of $a$ divided by $b$, and $a \% b$ denotes the remainder of $a$ divided by $b$.

Given that the minimum number of operations is guaranteed to be within 24, output the minimum number of operations needed to solve the puzzle.

Input Format

The input is given from the standard input in the following format:

$H$ $W$ $c_{1,1}$ $c_{1,2}$ … $c_{1,W}$ $c_{2,1}$ $c_{2,2}$ … $c_{2,W}$ : $c_{H,1}$ $c_{H,2}$ … $c_{H,W}$

• The first line contains two integers $H\ (2 \leq H \leq 6)$ and $W\ (2 \leq W \leq 6)$, representing the dimensions of the puzzle board.
• The next $H$ lines contain the information of the puzzle board. The $i$-th line contains integers $c_{i,1}, c_{i,2}, ..., c_{i,W}$ separated by spaces, representing the numbers written on the cells at coordinates $(i,1), (i,2), ..., (i,W)$. A cell with $c_{i,j} = 0$ represents an empty cell.
• The puzzle board is guaranteed to contain exactly one each of the integers from $1$ to $H \times W - 1$ and one $0$ representing the empty cell.
• The minimum number of operations to solve the puzzle is guaranteed to be within 24.

Output Format

Output a single line containing the minimum number of operations needed to solve the puzzle. Do not forget the newline at the end.

Sample Input and Output

Sample Input #1

3 3
1 0 2
4 5 3
7 8 6

Sample Output #1

3

Sample Input #2

3 5
6 1 2 8 5
7 0 4 3 10
11 12 13 9 14

Sample Output #2

12

Sample Input #3

2 2
1 2
3 0

Sample Output #3

0

Sample Input #4

4 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0

Sample Output #4

0

Sample Input #5

6 6
1 2 3 4 5 6
14 15 10 16 11 12
8 9 19 17 0 18
7 13 20 22 23 24
25 26 21 28 29 30
31 32 27 33 34 35

Sample Output #5

24

Notes/Hints

Sample Explanation 1

Initially, the empty cell is at $(1,2)$. By moving the empty cell "right → down → down", the completed state can be achieved with the minimum number of operations.

Sample Explanation 4

The puzzle might already be completed from the start.

Sample Explanation 5

This is a case where the maximum number of operations is required.

见题面 Input 部分

见题面 Output 部分