- Time limit: 1.00 s
- Memory limit: 512 MB
The grid cells have to be labeled with numbers 1, 2, 3 and 4. There is only one rule: neighbors must have different labels. So you cannot have e.g. a cell with label 1 if there is another cell with label 1 above it, below it, or on its left or right side.
In the input, some of the grid cells are already labeled. All labeled cells already follow the rule that neighbors have different labels.
However, some input cells may be empty. The empty cells form a connected region in the following sense: you can pick any two empty cells $x$ and $y$, and you can walk from $x$ to $y$ so that you step from one empty cell to a neighboring empty cell.
Now your task is to find a way to label all cells with labels 1, 2, 3, and 4 so that as many cells as possible can keep their original labels.
The first input line contains two positive integers $n$ and $m$.
Then there are $n$ lines, each of which contains $m$ characters. Each character denotes the input label of one cell: either it is 0 (empty), or one of the values 1, 2, 3, and 4 to indicate a cell that is already labeled.
Print the final grid where every cell is labeled. You can print any valid solution.
- $1 \le n \cdot m \le 10^5$
Explanation: All 9 non-empty cells were able to keep their original labels.
Explanation: There is no way to label the grid so that 8 cells have their original labels, but there is a way to label the grid so that 7 cells have their original labels.