One-Four Overload (Codeforces 1567F)
Tags: Others, 2-sat

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$$$.  Alice couldn't figure it out, so she asks Bob to help her. Help Bob find any such grid, or state that no such grid exists.

Input: 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: Output "'NO" if no suitable grid exists. Otherwise, output "'YES"'. Then output $$$n$$$ lines of $$$m$$$ space-separated integers — the integers in the grid.

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

Sample Inputs:
5 5
.....
.XXX.
.X.X.
.XXX.
.....

5 5
.....
.XXX.
.XXX.
.XXX.
.....

3 2
..
..
..

9 9
.........
.XXXXX.X.
.X...X...
.X.XXXXX.
.X.X.X.X.
.X.XXX.X.
.X.....X.
.XXXXXXX.
.........

Sample Outputs:
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

NO

YES
4 1
4 1
1 4

YES
4 4 4 1 4 1 4 1 4
1 5 5 5 5 5 4 10 1
4 5 1 4 1 5 4 4 4
4 5 1 5 5 0 5 5 1
4 5 1 5 4 5 1 5 4
4 5 1 5 5 5 4 5 1
1 5 4 4 1 1 4 5 1
4 5 5 5 5 5 5 5 4
1 1 1 1 4 4 1 1 4

Solution (Python):
from collections import defaultdict
(m, n) = [int(i) for i in input().split()]
d = ['' for i in range(m)]
for i in range(m):
    d[i] = input()
op = defaultdict(list)
r = [[-1] * n for i in range(m)]
for i in range(m):
    for j in range(n):
        if d[i][j] == 'X':
            t = []
            for (a, b) in [(i, j - 1), (i - 1, j), (i, j + 1), (i + 1, j)]:
                if 0 <= a < m and 0 <= b < n and (d[a][b] == '.'):
                    t.append((a, b))
            if len(t) % 2:
                print('NO')
                exit()
            if len(t) == 0:
                r[i][j] = 0
            if len(t) == 2:
                op[t[0]].append(t[1])
                op[t[1]].append(t[0])
                r[i][j] = 5
            if len(t) == 4:
                op[t[0]].append(t[1])
                op[t[1]].append(t[0])
                op[t[2]].append(t[3])
                op[t[3]].append(t[2])
                r[i][j] = 10
for a in range(m):
    for b in range(n):
        if r[a][b] == -1:
            r[a][b] = 1
            st = [(a, b)]
            while st:
                (i, j) = st.pop()
                for (x, y) in op[i, j]:
                    if r[x][y] == -1:
                        r[x][y] = 5 - r[i][j]
                        st.append((x, y))
                    elif r[x][y] != 5 - r[i][j]:
                        print('NO')
                        exit()
print('YES')
for i in range(m):
    print(' '.join(('1' if r[i][j] == -1 else str(r[i][j]) for j in range(n))))

Solution (Python):
from collections import defaultdict
(m, n) = [int(i) for i in input().split()]
d = ['' for i in range(m)]
for i in range(m):
    d[i] = input()
op = defaultdict(list)
r = [[-1] * n for i in range(m)]
for i in range(m):
    for j in range(n):
        if d[i][j] == 'X':
            t = []
            for (a, b) in [(i, j - 1), (i - 1, j), (i, j + 1), (i + 1, j)]:
                if 0 <= a < m and 0 <= b < n and (d[a][b] == '.'):
                    t.append((a, b))
            if len(t) % 2:
                print('NO')
                exit()
            if len(t) == 0:
                r[i][j] = 0
            if len(t) == 2:
                op[t[0]].append(t[1])
                op[t[1]].append(t[0])
                r[i][j] = 5
            if len(t) == 4:
                op[t[0]].append(t[1])
                op[t[1]].append(t[0])
                op[t[2]].append(t[3])
                op[t[3]].append(t[2])
                r[i][j] = 10
for a in range(m):
    for b in range(n):
        if r[a][b] == -1:
            r[a][b] = 1
            st = [(a, b)]
            while st:
                (i, j) = st.pop()
                for (x, y) in op[i, j]:
                    if r[x][y] == -1:
                        r[x][y] = 5 - r[i][j]
                        st.append((x, y))
                    elif r[x][y] != 5 - r[i][j]:
                        print('NO')
                        exit()
print('YES')
for i in range(m):
    print(' '.join(('1' if r[i][j] == -1 else str(r[i][j]) for j in range(n))))

Solution (Python):
from collections import defaultdict
(m, n) = [int(i) for i in input().split()]
d = ['' for i in range(m)]
for i in range(m):
    d[i] = input()
op = defaultdict(list)
r = [[-1] * n for i in range(m)]
for i in range(m):
    for j in range(n):
        if d[i][j] == 'X':
            t = []
            for (a, b) in [(i, j - 1), (i - 1, j), (i, j + 1), (i + 1, j)]:
                if 0 <= a < m and 0 <= b < n and (d[a][b] == '.'):
                    t.append((a, b))
            if len(t) % 2:
                print('NO')
                exit()
            if len(t) == 0:
                r[i][j] = 0
            if len(t) == 2:
                op[t[0]].append(t[1])
                op[t[1]].append(t[0])
                r[i][j] = 5
            if len(t) == 4:
                op[t[0]].append(t[1])
                op[t[1]].append(t[0])
                op[t[2]].append(t[3])
                op[t[3]].append(t[2])
                r[i][j] = 10
for a in range(m):
    for b in range(n):
        if r[a][b] == -1:
            r[a][b] = 1
            st = [(a, b)]
            while st:
                (i, j) = st.pop()
                for (x, y) in op[i, j]:
                    if r[x][y] == -1:
                        r[x][y] = 5 - r[i][j]
                        st.append((x, y))
                    elif r[x][y] != 5 - r[i][j]:
                        print('NO')
                        exit()
print('YES')
for i in range(m):
    print(' '.join(('1' if r[i][j] == -1 else str(r[i][j]) for j in range(n))))