問題一覧 > 通常問題

No.3732 Labyrinth Maker

レベル : / AI推定難易度 : 2100 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 28
作問者 : 👑 kencho / テスター : uruzunyaa 👑 p-adic
お気に入りにしたユーザー ProblemId : 13617 / 自分の提出
問題文最終更新日: 2026-11-02 04:27:49
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
グリッド構築24題 (順位表) の他の問題:

Problem Statement

kencho loves the number $N$ and grids.

The floor plan of kencho's house consists of square small rooms arranged in $N$ rows and $N$ columns, and the small room in the $i$-th row from the top and the $j$-th column from the left contains $A_{i, j}$ pieces of furniture.

kencho was satisfied with this house at first, but he has come to want the number of rooms and the number of pieces of furniture in each room to be related to his beloved $N$. So he has decided to tear down some of the walls between adjacent small rooms, combining small rooms into rooms. Each original small room is not divided and belongs to exactly $1$ room.

kencho wants to make a floor plan that satisfies all of the following conditions.

  • The number of rooms is exactly $N$.
  • Each room consists of $1$ or more small rooms and is connected.
  • The total number of pieces of furniture in each room is a multiple of $N$.

Here, a room is connected if, for any $2$ small rooms belonging to the same room, it is possible to move from one to the other by moving up, down, left, or right through only small rooms belonging to that same room.

Also, all the furniture is firmly glued to the floor and cannot be moved.

Tell kencho a floor plan that satisfies the conditions. If no floor plan satisfying the conditions exists, print -1.

You are given $T$ test cases; print the answer for each of them.

Constraints

  • All input values are integers.
  • $1 \leq T \leq 10^5$
  • $2 \leq N \leq 1000$
  • $1 \leq A_{i, j} \leq N$
  • The sum of $N^2$ in $1$ input file does not exceed $10^6$.

Input

The input is given from standard input in the following format. Here, $case_i$ denotes the $i$-th case.

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

Each test case is given in the following format.

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

Output

For each case, if a floor plan satisfying the conditions exists, print one example in the following format.

Assign the numbers from $1$ to $N$ to the $N$ rooms you made, without duplicates. $B_{i, j}$ represents the number of the room to which the small room in the $i$-th row from the top and the $j$-th column from the left belongs.

Note that $1 \leq B_{i, j} \leq N$ must hold and each room must be connected. Also, for each integer $k$ between $1$ and $N$, inclusive, there must be $1$ or more $(i, j)$ such that $B_{i, j} = k$ (see also Sample $1$).

$B_{1, 1}\ B_{1, 2}\ \ldots\ B_{1, N}$
$B_{2, 1}\ B_{2, 2}\ \ldots\ B_{2, N}$
$\vdots$
$B_{N, 1}\ B_{N, 2}\ \ldots\ B_{N, N}$

If no floor plan satisfying the conditions exists, print -1.

Print a newline at the end of the output for each case.

Visualizer

A web-based visualizer for the output is available here.

During the contest, sharing visualization results and mentioning solutions or considerations are prohibited. Please be careful.

Also, as a rule, questions about the specifications of the visualizer are not accepted. Please use it only as an auxiliary tool.

Sample

Sample 1
Input
2
3
2 1 1
3 2 2
1 1 2
2
1 2
1 1
Output
1 1 2
1 3 2
3 3 3
-1

Let us explain the first test case.

In the new floor plan, room $1$ has $6$ pieces of furniture, room $2$ has $3$ pieces, and room $3$ has $6$ pieces, all of which are multiples of $3$, so this output is correct.

The division into rooms and the placement of the furniture are as shown in the following figure.



The following output example is incorrect because room $1$ is split into multiple parts and is not connected.
1 3 3
2 1 3
1 1 3

The following output example is incorrect because there is no region belonging to room $2$, which violates the condition that there are exactly $N$ rooms.

1 3 3
1 1 3
1 1 3

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