No.3734 No Flat Notes
Problem Statement
Write integers in the cells of an $H \times W$ grid so that the following $2$ conditions are satisfied.
- Each cell contains exactly $1$ integer.
- Each integer between $1$ and $HW$, inclusive, is written in exactly $1$ cell.
In other words, the integers are written so that the $HW$ integers between $1$ and $HW$, inclusive, and the $HW$ cells are in $1$-to-$1$ correspondence.
A cell is called a peak cell if the integer written in it is greater than the integers written in all of its vertically and horizontally adjacent cells.
A cell is called a valley cell if the integer written in it is less than the integers written in all of its vertically and horizontally adjacent cells.
Find one way of writing the numbers such that the number of peak cells and the number of valley cells are each exactly $M$. If no such way exists, print -1.
Constraints
- All input values are integers.
- $1 \leq H, W \leq 500$
- $2 \leq HW$
- $0 \leq 2M \leq HW$
Partial Score
This problem has partial scoring based on subtasks.
| Subtask | Score | Constraints |
|---|---|---|
| 部分点 | 20% (70 pts) | $H,\ W$ は偶数 |
| 満点 | 80% (280 pts) | 追加の制約は無い |
Input
The input is given from standard input in the following format.
$H\ W\ M$
Output
If a way of writing satisfying the conditions exists, print one such way in the following format, where $A_{i, j}$ is the integer written in the cell at the $i$-th row from the top and the $j$-th column from the left of the grid. If no way of writing satisfying the conditions exists, print -1.
$A_{1, 1}\ A_{1, 2}\ \ldots\ A_{1, W}$
$A_{2, 1}\ A_{2, 2}\ \ldots\ A_{2, W}$
$\vdots$
$A_{H, 1}\ A_{H, 2}\ \ldots\ A_{H, W}$
Print a newline at the end.
Visualizer
A web-based visualizer for the output is available here.
During the contest, sharing visualization results and mentioning solutions or analysis are prohibited. Please be careful.
In principle, questions about the specifications of the visualizer are not accepted. Please use it only as an auxiliary tool.
Sample
Sample 1
Input
2 4 2
Output
3 1 8 7 4 2 6 5
The sample output is as shown in the figure below: the $4, 8$ cells, $2$ cells in total, are peak cells, and the $1, 5$ cells, $2$ cells in total, are valley cells.
This test case is included in the subtask cases.
Sample 2
Input
3 3 3
Output
2 4 1 9 3 6 7 5 8
The sample output is as shown in the figure below: the $4, 9, 8$ cells, $3$ cells in total, are peak cells, and the $2, 1, 3$ cells, $3$ cells in total, are valley cells.
This test case is not included in the subtask cases.
Sample 3
Input
2 1 0
Output
-1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。