One-Four Overload
Contest: Codeforces Round 742 (Div. 2)
Difficulty rating: 2700
Tags: 2-sat, constructive algorithms, dfs and similar, dsu, graphs, implementation

Alice has an empty grid with $$$n$$$ rows and $$$m$$$ columns. Some of the cells are marked, and no marked cells are adjacent to the edge of the grid. (Two squares are adjacent if they share a side.)

Alice wants to fill each cell with a number such that the following statements are true:

- every unmarked cell contains either the number $$$1$$$ or $$$4$$$;
- every marked cell contains the sum of the numbers in all unmarked cells adjacent to it (if a marked cell is not adjacent to any unmarked cell, this sum is $$$0$$$);
- every marked cell contains a multiple of $$$5$$$.

Input format:
The first line of input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 500$$$) — the number of rows and the number of columns in the grid, respectively.

Then $$$n$$$ lines follow, each containing $$$m$$$ characters. Each of these characters is either '.' or 'X' — an unmarked and a marked cell, respectively. No marked cells are adjacent to the edge of the grid.

Output format:
Output "'NO" if no suitable grid exists. Otherwise, output "'YES"'. Then output $$$n$$$ lines of $$$m$$$ space-separated integers — the integers in the grid.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
It can be shown that no such grid exists for the second test.

Example input:
5 5
.....
.XXX.
.X.X.
.XXX.
.....

Example output:
YES
4 1 4 4 1
4 5 5 5 1
4 5 1 5 4
1 5 5 5 4
1 4 4 1 4

Example input:
5 5
.....
.XXX.
.XXX.
.XXX.
.....

Example output:
NO

Editorial:
Let's look at the numbers in the grid modulo $$$5$$$. $$$1$$$ and $$$4$$$ are $$$1$$$ and $$$-1$$$ modulo $$$5$$$, and by definition each marked cell must be $$$0$$$ modulo $$$5$$$. This means that each marked cell must have an even number of unmarked neighbors, and there must be an equal number of $$$1$$$s and $$$4$$$s among those neighbors.
In other words, the problem is about two-coloring a grid so each marked square has the same number of red and blue neighbors. If each cell is adjacent to 2 or 4 unmarked cells, then they will form a graph whose faces are two-colorable (the proof of this is below), which will satisfy all conditions, since all cells adjacent to 2 unmarked cells will be adjacent to two cells on opposite faces. However, the tricky case is to deal with cells with 0 unmarked neighbors.
The idea is to put a "mask" on top of the grid, which will also allow the cells with no unmarked neighbors to satisfy the condition while not interfering with already placed cells. That is, in the coloring terminology above, we will two color the grid, and then flip some cells according to the "mask" such that
• all cells with 2 or 4 unmarked neighbors still satisfy the condition, and
• all cells with 0 unmarked neighbors now satisfy the condition.
We claim that we should flip all cells in all even-numbered columns; that is, the mask should contain columns alternately colored red and blue. Let's prove this works.
There are four types of marked cells:
• a marked cell with no marked neighbors: all four neighbors are in same connected component, so none of them will be "flipped" with respect to the rest, and they will work: they will be the numbers $$$1,4,1,4$$$ by the mask. For this to hold true, when we make connected components, we need to DFS/BFS diagonally as well.
• a marked cell with only marked neighors: nothing to check.
• a marked cell with marked neighbors in the shape of an L tromino: again, these unmarked cells must be part of same connected component, so they will work: they will be the numbers $$$1$$$ and $$$4$$$ by the mask. For this to hold true, when we make connected components, we need to DFS/BFS diagonally as well.
• a marked cell with marked neighbors in the shape of an I tromino: then the cell on one side is necessarily in a different connected component than the other, so one will be flipped by the two-coloring, and they will be the right parities.
It suffices to show that the graph formed by edges between connected components of unmarked cells is bipartite.
Consider instead the graph formed by the marked cells, with an edge between orthogonally adjacent cells. Consider each connected component of this graph individually. By the condition all vertices have degree 0, 2, or 4, but none can have degree 0 because the graph is connected. Now by a theorem of Euler this graph must have a Eulerian cycle.
Now we have a more general claim: the face-vertex dual of a Eulerian graph is bipartite. Suppose otherwise. Then the dual has some odd cycle. This means that some face of the dual must be bounded by an odd number of edges, since you can never "split" an odd cycle into only even ones. Also, the dual is planar, because our original graph is obviously planar (we are given an explicit planar embedding of it!).
Now some face of the dual has an odd number of edges. This means that in the dual graph of the dual, some vertex has odd degree. But the dual graph of the dual is the original graph. So the original graph is both Eulerian and has odd degree, which is absurd.
Finally, even though there are many connected components, it is clear that they do not interact: just set the infinite outside face to be one color, and the rest of the faces will be colored automatically.
Therefore this graph is bipartite, so we can two-color as desired, and we are done. Time complexity: $$$\mathcal{O}(mn)$$$.