#C5686. Fill the Garden Grid
Fill the Garden Grid
Fill the Garden Grid
You are given a garden represented as an n × m grid. Some cells already contain a pre‐filled flower represented by -1
, while other cells are empty (denoted by 0
). Your task is to fill every empty cell with an integer between 1 and n*m such that no number appears more than once in any row or any column. Note that the flowers (-1
) must remain unchanged.
The constraints can be summarized as follows:
- Each empty cell (value 0) must be replaced by a number in the range \(1\) to \(n \times m\).
- In every row, the filled numbers must be unique (ignoring the cells with \(-1\)).
- In every column, the filled numbers must be unique (ignoring the cells with \(-1\)).
- Cells with \(-1\) indicate flowers and must remain unchanged.
Implement a function to complete the garden grid following these rules. It is guaranteed that at least one solution exists.
inputFormat
The input is read from standard input and has the following format:
n m row_1 row_2 ... row_n
Where n
and m
are integers representing the number of rows and columns, respectively. Each of the following n
lines contains m
space‐separated integers. A value of -1
represents a flower (pre-filled cell), and 0
represents an empty cell that needs to be filled.
outputFormat
Output to standard output the completed grid in the same format as the input grid: n
lines each containing m
space-separated integers. The pre-filled cells (-1
) should remain unchanged, and all empty cells must be replaced by a number that satisfies the problem conditions.
3 3
0 -1 0
-1 0 -1
0 -1 0
1 -1 2
-1 1 -1
2 -1 1
</p>