/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
N \times N のマス目があります。このマス目の上から i 行目、左から j 列目をマス (i,j) と呼びます。
全てのマスに整数を 1 つずつ書き込む方法であって、以下の条件を満たすようなものを 1 つ求めてください。
- 1 以上 N^2 以下の整数がそれぞれちょうど 1 つずつ書き込まれる。
- すべての整数 i,j\, (1 \leq i,j \leq N) に対し、マス (i,j) が次の条件を満たす。
- マス (i,j) の上下左右斜めに隣接するマス(最大 8 個)のうち、書かれている整数がマス (i,j) に書かれている整数よりも大きいものの個数を a、小さいものの個数を b とする。この時、 a \neq b が成り立つ。
なお、この問題の制約の下、条件を満たす整数の書き込み方が必ず存在することが証明できます。
制約
- 2 \leq N \leq 500
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
条件をみたす整数の書き込み方を以下の形式で出力せよ。
x_{1,1} \ldots x_{1,N}
\vdots
x_{N,1} \ldots x_{N,N}
ただし、x_{i,j} はマス (i,j) に書き込まれる整数とする。
答えが複数存在する場合はどれを出力しても正解とみなされる。
入力例 1
2
出力例 1
1 2 3 4
この出力は 1 以上 N^2\, (=4) 以下の整数がそれぞれちょうど 1 つずつ書き込まれているため、1 つ目の条件を満たしています。
また、マス (1,1) の上下左右斜めに隣接するマスのうち書かれている整数がマス (1,1) に書かれているものより大きいものはマス (1,2)、マス (2,1)、マス (2,2) の 3 個で、小さいものは 0 個です。
このことからマス (1,1) に対しては a=3,b=0 となり、a\neq b が成り立ちます。
他のマスに対しても同様にして a\neq b が成り立つことが確かめられるため、この出力は 2 つ目の条件を満たしています。
以上より、この出力は正当です。
入力例 2
3
出力例 2
1 2 3 5 4 6 7 8 9
Score : 400 points
Problem Statement
We have an N \times N grid. Let (i,j) denote the square at the i-th row from the top and j-th column from the left in this grid.
Find one way to write an integer on every square to satisfy the conditions below.
- Each integer between 1 and N^2 is written exactly once.
- For every pair of integers i,j\, (1 \leq i,j \leq N), the square (i,j) satisfies the following.
- Among the squares horizontally, vertically, or diagonally adjacent to (i,j) (there are at most eight of them), let a and b be the number of squares with integers larger than and smaller than that of (i,j), respectively. Then, a \neq b holds.
Under the Constraints of this problem, it can be proved that such a way to write integers always exists.
Constraints
- 2 \leq N \leq 500
- N is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
Print a way to write integers to satisfy the conditions, in the following format:
x_{1,1} \ldots x_{1,N}
\vdots
x_{N,1} \ldots x_{N,N}
Here, x_{i,j} is the integer to write on the square (i,j).
If multiple solutions exist, any of them will be accepted.
Sample Input 1
2
Sample Output 1
1 2 3 4
This output contains each integer between 1 and N^2\, (=4) exactly once, so the first condition is satisfied.
Additionally, among the squares horizontally, vertically, or diagonally adjacent to the square (1,1), three squares (1,2), (2,1), and (2,2) have integers larger than that of (1,1), and none has an integer smaller than that.
Thus, for (1,1), we have a=3 and b=0, so a\neq b holds.
Similarly, it can be verified that a\neq b also holds for the other squares, so the second condition is satisfied.
Therefore, this output is valid.
Sample Input 2
3
Sample Output 2
1 2 3 5 4 6 7 8 9