yukicoder-283

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#!html
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});</script>
<script type="text/javascript" async src="http://10.71.10.90/sfiction/tool/MathJax/MathJax-master/MathJax.js?config=TeX-MML-AM_CHTML"></script>
<style>
.input, pre {
    display: block;
    padding: 9.5px;
    margin: 0 0 10px;
    font-size: 13px;
    line-height: 1.42857143;
    color: #333;
    word-break: break-all;
    word-wrap: break-word;
    background-color: #f5f5f5;
    border: 1px solid #ccc;
    border-radius: 4px;
}
</style>
}}}

== [https://yukicoder.me/problems/no/283 No.283 スライドパズルと魔方陣] ==

=== Description ===

{{{
#!html
<p>kamipeipaa非常喜欢<a href="https://en.wikipedia.org/wiki/Sliding_puzzle">滑块类游戏</a>和<a href="https://en.wikipedia.org/wiki/Magic_square">幻方</a>。</p>

<p>给出一个$N \times N$的滑块游戏，每个位置是$0$到$N^2-1$的数字，$0$表示空格子。你可以上下左右移动空格子任意次，然后把$N^2$填到空格子上。要求最后得到一个幻方。</p>
}}}

=== Input ===

{{{
#!html
<p class="input">
$N$<br>
$A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,N}$<br>
$A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,N}$<br>
$\vdots$<br>
$A_{N,1}$ $A_{N,2}$ $\dots$ $A_{N,N}$<br> 
</p>
<p>$1 \le N \le 50$。</p>
}}}

=== Output ===

{{{
#!html
<p>如果最后可以得到幻方，在第一行输出"possible"，然后输出一个合法的幻方。如果不可以，输出"impossible"。</p>
}}}

=== Sample ===

==== Sample 1 ====
输入
{{{
#!html
<pre>
3
8 1 6
3 5 7
4 0 2
</pre>
}}}
输出
{{{
#!html
<pre>
possible
8 1 6
3 5 7
4 9 2
</pre>
}}}

==== Sample 2 ====
输入
{{{
#!html
<pre>
3
8 1 6
3 0 7
4 5 2
</pre>
}}}
输出
{{{
#!html
<pre>
possible
8 1 6
3 5 7
4 9 2
</pre>
}}}

==== Sample 3 ====
输入
{{{
#!html
<pre>
2
0 1
2 3
</pre>
}}}
输出
{{{
#!html
<pre>
impossible
</pre>
}}}

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

Description

kamipeipaa非常喜欢滑块类游戏和幻方。

给出一个$N \times N$的滑块游戏，每个位置是$0$到$N^2-1$的数字，$0$表示空格子。你可以上下左右移动空格子任意次，然后把$N^2$填到空格子上。要求最后得到一个幻方。

Input

$N$
$A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,N}$
$A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,N}$
$\vdots$
$A_{N,1}$ $A_{N,2}$ $\dots$ $A_{N,N}$

$1 \le N \le 50$。

Output

如果最后可以得到幻方，在第一行输出"possible"，然后输出一个合法的幻方。如果不可以，输出"impossible"。

Sample

Sample 1

输入

38 1 63 5 74 0 2

输出

possible8 1 63 5 74 9 2

Sample 2

输入

38 1 63 0 74 5 2

输出

possible8 1 63 5 74 9 2

Sample 3

输入

20 12 3

输出

impossible