链接: https://cses.fi/problemset/task/1670

板块: Additional Problems I

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定一个 $3 \times 3$ 的网格，其中包含数字 $1,2,\dots,9$。你的任务是通过一系列移动，使网格变成如下样子：

$\begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{matrix}$

每一步，你可以交换任意两个相邻方格（水平或垂直相邻）中的数字。最少需要多少步？

输入

输入有三行，每行包含三个整数。

输出

输出一个整数：最少的移动步数。

数据范围

（题面未给出显式上下界）

样例输入

2 1 3
7 5 9
8 4 6

样例输出

4