Big Brush (Codeforces 1638D)
Tags: Greedy, data structures

You found a painting on a canvas of size $$$n \times m$$$. The canvas can be represented as a grid with $$$n$$$ rows and $$$m$$$ columns. Each cell has some color. Cell $$$(i, j)$$$ has color $$$c_{i,j}$$$.Near the painting you also found a brush in the shape of a $$$2 \times 2$$$ square, so the canvas was surely painted in the following way: initially, no cell was painted. Then, the following painting operation has been performed some number of times:  Choose two integers $$$i$$$ and $$$j$$$ ($$$1 \le i < n$$$, $$$1 \le j < m$$$) and some color $$$k$$$ ($$$1 \le k \le nm$$$).  Paint cells $$$(i, j)$$$, $$$(i + 1, j)$$$, $$$(i, j + 1)$$$, $$$(i + 1, j + 1)$$$ in color $$$k$$$. All cells must be painted at least once. A cell can be painted multiple times. In this case, its final color will be the last one.Find any sequence of at most $$$nm$$$ operations that could have led to the painting you found or state that it's impossible.

Input: The first line of input contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n, m \le 1000$$$) — the dimensions of the canvas.On the $$$i$$$-th of the next $$$n$$$ lines of input, there will be $$$m$$$ integers. The $$$j$$$-th of them is $$$a_{i,j}$$$ ($$$1 \le a_{i,j} \le nm$$$) — the color of cell $$$(i, j)$$$.

Output: If there is no solution, print a single integer $$$-1$$$.Otherwise, on the first line, print one integer $$$q$$$ ($$$1 \le q \le nm$$$) — the number of operations.Next, print the operations in order. On the $$$k$$$-th of the next $$$q$$$ lines, print three integers $$$i$$$, $$$j$$$, $$$c$$$ ($$$1 \le i < n$$$, $$$1 \le j < m$$$, $$$1 \le c \le nm$$$) — the description of the $$$k$$$-th operation.If there are multiple solutions, print any.

Note: In the first test case, the solution is not unique. Here's one of them:  In the second test case, there is no way one could obtain the given painting, thus the answer is $$$-1$$$.

Sample Inputs:
4 4
5 5 3 3
1 1 5 3
2 2 5 4
2 2 4 4

3 4
1 1 1 1
2 2 3 1
2 2 1 1

Sample Outputs:
6
1 3 3
3 3 4
2 2 5
1 1 5
2 1 1
3 1 2

-1

Solution (Python):
import os, sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
Z = lambda : sys.stdin.readline().rstrip('\r\n')
Y = lambda : map(int, Z().split())
Q = lambda x: print(x) or quit()
P = lambda x, y: (x + y, x + y + 1, x + y + 1024, x + y + 1025)
(n, m) = Y()
a = []
O = []
mm = m - 1
nN = n * 1024 - 1024
q = []
nq = []
u = [0] * (n * 1024)
for _ in range(n):
    a.extend(Y())
    a.extend([0] * (1024 - m))
for x in range(0, nN, 1024):
    for y in range(mm):
        c = 0
        for i in P(x, y):
            if c and a[i] and (a[i] != c):
                break
            elif not c and a[i]:
                c = a[i]
        else:
            q.append(x + y)
            u[x + y] = 1
D = [*zip((-1024, -1024, -1024, 0, 1024, 1024, 1024, 0), (-1, 0, 1, 1, 1, 0, -1, -1))]
while q:
    v = q.pop()
    y = v & 1023
    x = v - y
    c = 0
    for i in P(x, y):
        if a[i] > c:
            c = a[i]
        a[i] = 0
    if c:
        O.append(f'{1 + (x >> 10)} {1 + y} {c}')
        for (dx, dy) in D:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < nN and 0 <= ny < mm and (not u[nx + ny]):
                c = 0
                for i in P(nx, ny):
                    if c and a[i] and (a[i] != c):
                        break
                    elif not c and a[i]:
                        c = a[i]
                else:
                    if c:
                        u[nx + ny] = 1
                        nq.append(nx + ny)
    if not q:
        (q, nq) = (nq, [])
if any(a):
    Q(-1)
print(len(O))
print('\n'.join(reversed(O)))

Solution (Python):
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def solve():
    (n, m) = map(int, input().split())
    MAP = [list(map(int, input().split())) for i in range(n)]
    ANS = []
    USE = [[0] * m for i in range(n)]
    Q = []
    for i in range(n - 1):
        for j in range(m - 1):
            if MAP[i][j] == MAP[i + 1][j] == MAP[i][j + 1] == MAP[i + 1][j + 1]:
                ANS.append((i, j, MAP[i][j]))
                USE[i][j] = 1
                USE[i + 1][j] = 1
                USE[i][j + 1] = 1
                USE[i + 1][j + 1] = 1
                Q.append((i, j))
                Q.append((i + 1, j))
                Q.append((i, j + 1))
                Q.append((i + 1, j + 1))
    while Q:
        (x, y) = Q.pop()
        if 0 <= x + 1 < n and 0 <= y + 1 < m:
            C = []
            for (z, w) in [(x, y), (x + 1, y), (x, y + 1), (x + 1, y + 1)]:
                if USE[z][w] == 1:
                    continue
                else:
                    C.append(MAP[z][w])
            if len(set(C)) == 1:
                ANS.append((x, y, C[0]))
                for (z, w) in [(x, y), (x + 1, y), (x, y + 1), (x + 1, y + 1)]:
                    if USE[z][w] == 0:
                        USE[z][w] = 1
                        Q.append((z, w))
        if 0 <= x - 1 < n and 0 <= y - 1 < m:
            C = []
            for (z, w) in [(x - 1, y - 1), (x, y - 1), (x - 1, y), (x, y)]:
                if USE[z][w] == 1:
                    continue
                else:
                    C.append(MAP[z][w])
            if len(set(C)) == 1:
                ANS.append((x - 1, y - 1, C[0]))
                for (z, w) in [(x - 1, y - 1), (x, y - 1), (x - 1, y), (x, y)]:
                    if USE[z][w] == 0:
                        USE[z][w] = 1
                        Q.append((z, w))
        if 0 <= x + 1 < n and 0 <= y - 1 < m:
            C = []
            for (z, w) in [(x, y - 1), (x + 1, y - 1), (x, y), (x + 1, y)]:
                if USE[z][w] == 1:
                    continue
                else:
                    C.append(MAP[z][w])
            if len(set(C)) == 1:
                ANS.append((x, y - 1, C[0]))
                for (z, w) in [(x, y - 1), (x + 1, y - 1), (x, y), (x + 1, y)]:
                    if USE[z][w] == 0:
                        USE[z][w] = 1
                        Q.append((z, w))
        if 0 <= x - 1 < n and 0 <= y + 1 < m:
            C = []
            for (z, w) in [(x - 1, y), (x, y), (x - 1, y + 1), (x, y + 1)]:
                if USE[z][w] == 1:
                    continue
                else:
                    C.append(MAP[z][w])
            if len(set(C)) == 1:
                ANS.append((x - 1, y, C[0]))
                for (z, w) in [(x - 1, y), (x, y), (x - 1, y + 1), (x, y + 1)]:
                    if USE[z][w] == 0:
                        USE[z][w] = 1
                        Q.append((z, w))
    count = 0
    for i in range(n):
        for j in range(m):
            if USE[i][j] == 1:
                count += 1
    if count == n * m:
        print(len(ANS))
        LANS = []
        for (x, y, z) in ANS[::-1]:
            LANS.append(str(x + 1) + ' ' + str(y + 1) + ' ' + str(z))
        sys.stdout.write('\n'.join(LANS))
    else:
        print(-1)
solve()

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import deque
directions = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]

def solve(a, n, m):

    def valid(i, j):
        v = 0
        if a[i][j] != 0:
            v = a[i][j]
        if a[i + 1][j] != 0:
            if v == 0:
                v = a[i + 1][j]
            elif v != a[i + 1][j]:
                return 0
        if a[i][j + 1] != 0:
            if v == 0:
                v = a[i][j + 1]
            elif v != a[i][j + 1]:
                return 0
        if a[i + 1][j + 1] != 0:
            if v == 0:
                v = a[i + 1][j + 1]
            elif v != a[i + 1][j + 1]:
                return 0
        return v
    bfs = deque()
    res = list()
    vis = [[0 for _ in range(m)] for _ in range(n)]
    for i in range(n - 1):
        for j in range(m - 1):
            if a[i][j] == a[i + 1][j] and a[i][j] == a[i][j + 1] and (a[i][j] == a[i + 1][j + 1]):
                if i >= 1 and vis[i - 1][j] == 1:
                    continue
                if j >= 1 and vis[i][j - 1] == 1:
                    continue
                if i >= 1 and j >= 1 and (vis[i - 1][j - 1] == 1):
                    continue
                bfs.append([i, j])
                vis[i][j] = 1
    while len(bfs) > 0:
        node = bfs[0]
        bfs.popleft()
        collor = valid(node[0], node[1])
        if collor == 0:
            continue
        a[node[0]][node[1]] = 0
        a[node[0] + 1][node[1]] = 0
        a[node[0]][node[1] + 1] = 0
        a[node[0] + 1][node[1] + 1] = 0
        res.append([node[0], node[1], collor])
        for d in directions:
            x = node[0] + d[0]
            y = node[1] + d[1]
            if 0 <= x < n - 1 and 0 <= y < m - 1 and (vis[x][y] == 0) and valid(x, y):
                bfs.append([x, y])
                vis[x][y] = 1
    for i in range(n):
        for j in range(m):
            if a[i][j] != 0:
                print(-1)
                return
    res = res[::-1]
    print(len(res))
    for i in range(len(res)):
        print(res[i][0] + 1, res[i][1] + 1, res[i][2])
    ''
    return
(n, m) = list(map(int, input().split()))
a = list()
for i in range(n):
    a.append(list(map(int, input().split())))
solve(a, n, m)