問題文
你有垂直 H方形,水平 W 您将获得一块网格滑动拼图板(图 1)。

图 1. 滑动拼图板
每个方格都有不同的 数字高达 1 从 H×W-1 及更多 1 一格是空的。
在这个幻灯片拼图中,您可以用任何左侧、右侧、顶部或底部的方块替换空白方块。 但是,如果您要交换的方向上没有方块,则无法交换。
我想在此板上执行任意次数的交换操作以使其完成。 在这里,我希望完成的状态是这样的:正方形从左上角开始按顺序编号,右下角为空白(图 2)。

図2. 完成盤面
换句话说,完成的板面是
- 番号 i (1≦i≦H×W-1) 正方形是 位于 (1+[(i-1)÷W],1+(i-1)%W) 在
- 另外还有空格 指状态 (H,W) 在
。 该值除以[a÷b] 为 a 分成 b ,四舍五入到小数点, 指除以a%b 为 a 分成 b 后的余数。
最小操作次数为 24 如果保证在操作数之内,则打印解决难题所需的最小操作数。
入力
输入将以以下格式从标准输入给出。
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}
- 1 行包含一个整数,表示拼图板的垂直长度。 H (2≦H≦6) 和表示水平长度的整数 W (2≦W≦6) 用空格分隔。
- 2 从行 H 行提供有关拼图板的信息。这几天之一 i (1≦i≦H) 行显示幻灯片拼图的坐标。 代表正方形 (i,1),(i,2),...,(i,W) 中写入的数字的整数 c_{i,1},c_{i,2},...,c_{i,W} 用空格分隔。然而,c_{i,j}=0特别表明该方块是空的。
- 在拼图板上, 一个不超过1 从 H×W-1 的整数和一个代表空方格的整数 0 只是 1 保证一一出现。
- 解决该难题的最少操作次数为 保证在 24 次之内。 在
出力
1 行上,输出解决该难题的最少操作数。不要忘记最后的换行符。
入力例1
3 3 1 0 2 4 5 3 7 8 6
出力例1
3
首先,空方块是 它位于 (1,2) 。通过“右→下→下”移动这个空方块,就可以使其进入完成状态,此时你将达到最少的操作次数。
入力例2
3 5 6 1 2 8 5 7 0 4 3 10 11 12 13 9 14
出力例2
12
入力例3
2 2 1 2 3 0
出力例3
0
入力例4
4 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0
出力例4
0
有时拼图已经完成。
入力例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
出力例5
24
这是输出答案为最大值的情况。