パズルを解く
1から9までの数字が入った のグリッドを使い、下の図の形に配置を変えるための一連の入れ替え操作を行います。
各手順では、水平方向または垂直方向で隣り合う2つのマスを入れ替えることができます。
1 | 2 | 3 |
4 | 5 | 6 |
7 | 8 | 9 |
入力
3行の入力が与えられ、それぞれの行には初期のグリッドを表す3つの数字が含まれます。
出力
1, 2, 3, …, 9 のグリッドを完成させるために必要な移動回数の最小値を出力してください。
例
Input | Output |
|---|---|
2 1 3 7 5 9 8 4 6 | 4 |
Constraints
Time limit: 50 seconds
Memory limit: 512 MB
Output limit: 1 MB