#C5686. Fill the Garden Grid

    ID: 49362 Type: Default 1000ms 256MiB

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.

## sample
3 3
0 -1 0
-1 0 -1
0 -1 0
1 -1 2

-1 1 -1 2 -1 1

</p>