Making Everything White
Time limit1sMemory limit512 MB
Given an N by M black/white grid, choose for each cell one of three local color-inversion actions so that every cell ends up white, or report impossibility.
- Level
Hard8 of 10
- Topics
- Greedy, Implementation, Math, Matrix
- Solved
- No attempts yet
Problem
Each cell of an N by M grid is colored either white or black. For each cell, you can take one of the following three actions.
- Make no change.
- Invert the colors of all cells adjacent to the chosen cell. The chosen cell itself is not inverted.
- Invert the colors of the chosen cell and all cells adjacent to it.
Find a way to make every cell white.
Input
The first line gives N and M. (1 ≤ N, M ≤ 2,000)
The next N lines each give a string of length M describing one row. Every string consists of 'B' and 'W'. If the j-th character of the i-th line is 'B', that cell is black; if it is 'W', that cell is white.
Output
If making every cell white is impossible, print -1 on the first line.
Otherwise, print 1 on the first line, then print N lines, each containing M digits with no spaces.
The j-th digit of the i-th line describes the action taken on the cell in row i, column j. 1 means no change was made, 2 means all adjacent cells were inverted, and 3 means the cell and all adjacent cells were inverted.
If several valid answers exist, print any one of them.