No.839 Keep Distance and Nobody Explodes

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 47
作問者 : yamunakuyamunaku / テスター : heno_codeheno_code
4 ProblemId : 2617 / 出題時の順位表

フレーバーテキスト

信頼できる仲間との通信によって、あなたは爆弾解体に成功した!
残る仕事は解体した部品の運搬である。
危険から逃れ、すっかり安堵して準備を進めていたあなただったが、重大な問題が発覚した!
番号が隣り合う部品を不用意に近づけると、部品が再起動してしまうのだ!
爆弾ケースに部品を入れなおして運ぶ予定だったのだが、位置を工夫しなければ再び爆発の危機にさらされてしまう…

問題文

$N$ を正の

偶数

とし,$N \times N$ のグリッドを考えます.
グリッドの各マスに $1$ 以上 $N^2$ 以下の整数のうち $1$ つを書き込み,どの $2$ マスにも同じ数が書かれていないようにします.
グリッドの上から $i$ 番目,左から $j$ 番目のマスを $(i,j)$ と表すことにし,整数 $k\ (1 \le k \le N^2)$ が書かれたマスを $(X_k,Y_k)$ とします.
あなたの目標は,書き込まれた数の差が $1$ であるような $2$ マスの距離の最小値の最大化,すなわち,${\rm min}_{2 \le k \le N^2}\{(X_k-X_{k-1})^2+(Y_k-Y_{k-1})^2\}$ の最大化です.
これを達成する書き込み方を $1$ つ求めてください.

入力

$N$

  • $2 \le N \le 300$
  • $N$ は正の

    偶数

    である.

出力

問題文に沿うような書き込み方を $1$ つ出力してください.

具体的には,以下のように $N$ 行出力してください.
マス $(i,j)$ に書かれた整数を $A_{i,j}$ と表します.
$i$ 行目 $(1 \le i \le N)$ には, $N$ 個の整数 $A_{i,j}$ $(1 \le j \le N)$ を空白区切りで出力してください.

$
        \begin{matrix}
        A_{1,1} & A_{1,2} &  \cdots &  A_{1,N} \\
        A_{2,1} & A_{2,2} &  \cdots &  A_{2,N} \\
        \vdots  & \vdots  &         &  \vdots  \\
        A_{N,1} & A_{2,N} &  \cdots &  A_{N,N} 
        \end{matrix}
        $

サンプル

サンプル1
入力
2
出力
1 2
3 4

この出力では,
$(X_2-X_1)^2+(Y_2-Y_1)^2=1+0=1$
$(X_3-X_2)^2+(Y_3-Y_2)^2=1+1=2$
$(X_4-X_3)^2+(Y_4-Y_3)^2=1+0=1$
となります.
$N=2$ のとき,${\rm min}_{2 \le k \le N^2}\{(X_k-X_{k-1})^2+(Y_k-Y_{k-1})^2\}$ の値は必ず $1$ となるので,どの書き込み方を出力しても正答となります.

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。