問題一覧 > 通常問題

No.283 スライドパズルと魔方陣

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 128 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 15
作問者 : 紙ぺーぱー紙ぺーぱー
4 ProblemId : 664 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-07-20 13:58:54

問題文

kamipeipaa君はスライドパズル(参考)が好きですが魔方陣(参考)も好きです。
$N × N$のスライドパズルの盤面が与えられるので魔方陣を作ってみましょう。

$N × N$ マスの盤上に、$1$ から $N^{2}-1$ までの互いに相異なる整数が書かれた駒が並べられています。
空きマスの上下左右に隣接した駒を、空きマスにスライドして動かすことを繰り返すことができます。
空きマスに$N^{2}$の駒を入れることで完成したものとします。$N^2$の駒は空きマスでさえあればどこにでも置くことができるものとします。

入力

$N$
$A_{1,1}$ $A_{1,2}$ $…$ $A_{1,N}$
$A_{2,1}$ $A_{2,2}$ $…$ $A_{2,N}$
$⋮$
$A_{N,1}$ $A_{N,2}$ $…$ $A_{N,N}$

1行目にスライドパズルのサイズを表す整数$1 \le N \le 50$が与えられます。
$A_{i,j}$は$0$から$N^{2}-1$までの互いに相異なる整数であり、 $0$ は空きマスを表します。

出力

現在の盤面から魔方陣を作ることができるならば1行目に"possible"を出力し、続く$N$行に目標とする魔方陣を出力せよ。
魔方陣のフォーマットは入力と同様に1行に$N$個の要素を空白区切りで出力すればよい。
魔方陣を作ることができないならば"impossible"を出力せよ。

この問題はスペシャルジャッジである。魔方陣の盤面は現在の盤面から作れるものであれば、どれを出力してもよい。

サンプル

サンプル1
入力
3
8 1 6
3 5 7
4 0 2
出力
possible
8 1 6
3 5 7
4 9 2

0に9をはめると魔方陣になります。

サンプル2
入力
3
8 1 6
3 0 7
4 5 2
出力
possible
8 1 6
3 5 7
4 9 2

0のところに5をスライドさせ、9をはめると魔方陣になります。

サンプル3
入力
2
0 1
2 3
出力
impossible

不可能な場合はimpossibleのみを出力してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。