005 - Hちゃんのマイブーム

問題

某有名動画配信者のHちゃんは最近パズルで遊んでいる。

そのパズルとは3×3の9つのマスでできていて、その内1つがない。
その欠けている部分に隣接しているマスをスライドしてある盤面を目指すものだ。(下図参照)

本来このパズルでは目指す盤面は決まっているのだが、ずっとこのパズルで遊び、このパズルを極めつつあるHちゃんは決まった盤面を目指すだけでは飽きてしまいそうになった。
Hちゃんはこのパズルが好きだ。そのため、飽きたくない。飽きてしまった場合には「ふにー！」となってしまう。

しかし、だからといって1回のパズル遊びに時間をかけすぎるのもしゃくである。

そこで、Hちゃんの依頼によってあなたはパズルのはじめの盤面と目指す盤面が入力として与えられたとき、そのはじめの盤面から目指す盤面にするための最小手数を求めるプログラムを作ることになった。

入力

b1 b2 b3
b4 b5 b6
b7 b8 b9
e1 e2 e3
e4 e5 e6
e7 e8 e9

1行目から3行目にははじめの盤面 b₁ ~ b₉ が与えられる。
続く3行には目指す盤面の e₁ ~ e₉ が与えられる。
また、欠けているマスは'@'で表し、その他のマスは1~8の数字で表される。

出力

はじめの盤面から目指す盤面にするまでの最小手数を出力せよ。

制約

全てのマスにおいてかぶりはない。
また、はじめの盤面から目指す盤面になることがないということはないものとする。

さらに、採点用テストケースにおいて、初めの盤面から目指す盤面にするまで少なくとも25手は超えない。

入出力例

入力例1

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

出力例1

7

入力例2

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

出力例2

16