Polycarp and Snakes (Codeforces 1185E)
Tags: Implement, brute force

After a hard-working week Polycarp prefers to have fun. Polycarp's favorite entertainment is drawing snakes. He takes a rectangular checkered sheet of paper of size $$$n \times m$$$ (where $$$n$$$ is the number of rows, $$$m$$$ is the number of columns) and starts to draw snakes in cells.Polycarp draws snakes with lowercase Latin letters. He always draws the first snake with the symbol 'a', the second snake with the symbol 'b', the third snake with the symbol 'c' and so on. All snakes have their own unique symbol. There are only $$$26$$$ letters in the Latin alphabet, Polycarp is very tired and he doesn't want to invent new symbols, so the total number of drawn snakes doesn't exceed $$$26$$$.Since by the end of the week Polycarp is very tired, he draws snakes as straight lines without bends. So each snake is positioned either vertically or horizontally. Width of any snake equals $$$1$$$, i.e. each snake has size either $$$1 \times l$$$ or $$$l \times 1$$$, where $$$l$$$ is snake's length. Note that snakes can't bend.When Polycarp draws a new snake, he can use already occupied cells for drawing the snake. In this situation, he draws the snake "over the top" and overwrites the previous value in the cell.Recently when Polycarp was at work he found a checkered sheet of paper with Latin letters. He wants to know if it is possible to get this sheet of paper from an empty sheet by drawing some snakes according to the rules described above. If it is possible, he is interested in a way to draw snakes.

Input: The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases to solve. Then $$$t$$$ test cases follow.The first line of the test case description contains two integers $$$n$$$, $$$m$$$ ($$$1 \le n,m \le 2000$$$) — length and width of the checkered sheet of paper respectively.Next $$$n$$$ lines of test case description contain $$$m$$$ symbols, which are responsible for the content of the corresponding cell on the sheet. It can be either lowercase Latin letter or symbol dot ('.'), which stands for an empty cell.It is guaranteed that the total area of all sheets in one test doesn't exceed $$$4\cdot10^6$$$.

Output: Print the answer for each test case in the input.In the first line of the output for a test case print YES if it is possible to draw snakes, so that you can get a sheet of paper from the input. If it is impossible, print NO.If the answer to this question is positive, then print the way to draw snakes in the following format. In the next line print one integer $$$k$$$ ($$$0 \le k \le 26$$$) — number of snakes. Then print $$$k$$$ lines, in each line print four integers $$$r_{1,i}$$$, $$$c_{1,i}$$$, $$$r_{2,i}$$$ and $$$c_{2,i}$$$ — coordinates of extreme cells for the $$$i$$$-th snake ($$$1 \le r_{1,i}, r_{2,i} \le n$$$, $$$1 \le c_{1,i}, c_{2,i} \le m$$$). Snakes should be printed in order of their drawing. If there are multiple solutions, you are allowed to print any of them.Note that Polycarp starts drawing of snakes with an empty sheet of paper.


Sample Inputs:
1
5 6
...a..
..bbb.
...a..
.cccc.
...a..

3
3 3
...
...
...
4 4
..c.
adda
bbcb
....
3 5
..b..
aaaaa
..b..

2
3 3
...
.a.
...
2 2
bb
cc

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

YES
0
YES
4
2 1 2 4
3 1 3 4
1 3 3 3
2 2 2 3
NO

YES
1
2 2 2 2
YES
3
1 1 1 2
1 1 1 2
2 1 2 2

Solution (Python):
import sys
t = int(input())
for ti in range(t):
    (n, m) = map(int, input().split())
    a = []
    for i in range(n):
        a.append(input())
    top = {}
    bot = {}
    l = {}
    r = {}
    res = True
    for y in range(n):
        for x in range(m):
            c = a[y][x]
            if c != '.':
                if c not in top:
                    top[c] = y
                    bot[c] = y
                    l[c] = x
                    r[c] = x
                elif top[c] == y:
                    r[c] = x
                    xi = x - 1
                    while xi >= 0 and a[y][xi] != c:
                        if a[y][xi] == '.' or a[y][xi] < c:
                            res = False
                        xi -= 1
                elif l[c] == x and r[c] == x:
                    bot[c] = y
                    yi = y - 1
                    while yi >= 0 and a[yi][x] != c:
                        if a[yi][x] == '.' or a[yi][x] < c:
                            res = False
                        yi -= 1
                else:
                    res = False
    if len(top) == 0:
        sys.stdout.write('YES\n')
        sys.stdout.write('0\n')
    elif res:
        mxc = max(top)
        cnt = ord(mxc) & 31
        sys.stdout.write('YES\n')
        sys.stdout.write(str(cnt) + '\n')
        for i in range(cnt):
            ci = chr(ord('a') + i)
            if ci not in top:
                ci = mxc
            sys.stdout.write(f'{top[ci] + 1} {l[ci] + 1} {bot[ci] + 1} {r[ci] + 1}\n')
    else:
        sys.stdout.write('NO\n')

Solution (Python):
import random, sys, os, math, gc
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce, cmp_to_key
from itertools import accumulate, combinations, permutations, product
from heapq import nsmallest, nlargest, heapify, heappop, heappush
from io import BytesIO, IOBase
from copy import deepcopy
from bisect import bisect_left, bisect_right
from math import factorial, gcd
from operator import mul, xor
from types import GeneratorType
BUFSIZE = 8192
MOD = 10 ** 9 + 7
MODD = 998244353
INF = float('inf')
D4 = [(1, 0), (0, 1), (-1, 0), (0, -1)]
D8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

def solve():
    (n, m) = LII()
    arr = [list(I()) for _ in range(n)]
    pos = [[] for _ in range(26)]
    for i in range(n):
        for j in range(m):
            if arr[i][j] != '.':
                pos[ord(arr[i][j]) - 97].append((i, j))
    ans = [() for _ in range(26)]
    for ch in range(25, -1, -1):
        if not pos[ch]:
            continue
        if pos[ch][0][0] != pos[ch][-1][0] and pos[ch][0][1] != pos[ch][-1][1]:
            return print('NO')
        ans[ch] = pos[ch][0] + pos[ch][-1]
    del pos
    narr = [['.'] * m for _ in range(n)]
    for i in range(26):
        if not ans[i]:
            continue
        (x1, y1, x2, y2) = ans[i]
        (x, y) = (x1, y1)
        while x != x2 or y != y2:
            narr[x][y] = chr(i + 97)
            if x < x2:
                x += 1
            if y < y2:
                y += 1
        narr[x2][y2] = chr(i + 97)
    if arr != narr:
        return print('NO')
    del narr
    while ans and (not ans[-1]):
        ans.pop()
    print('YES')
    print(len(ans))
    for i in range(len(ans)):
        if not ans[i]:
            (x1, y1, x2, y2) = ans[-1]
            print(*[x + 1 for x in [x1, y1, x2, y2]])
            continue
        (x1, y1, x2, y2) = ans[i]
        print(*[x + 1 for x in [x1, y1, x2, y2]])

def main():
    t = 1
    t = II()
    for _ in range(t):
        solve()

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

def bitcnt(n):
    c = (n & 6148914691236517205) + (n >> 1 & 6148914691236517205)
    c = (c & 3689348814741910323) + (c >> 2 & 3689348814741910323)
    c = (c & 1085102592571150095) + (c >> 4 & 1085102592571150095)
    c = (c & 71777214294589695) + (c >> 8 & 71777214294589695)
    c = (c & 281470681808895) + (c >> 16 & 281470681808895)
    c = (c & 4294967295) + (c >> 32 & 4294967295)
    return c

def lcm(x, y):
    return x * y // gcd(x, y)

def lowbit(x):
    return x & -x

def perm(n, r):
    return factorial(n) // factorial(n - r) if n >= r else 0

def comb(n, r):
    return factorial(n) // (factorial(r) * factorial(n - r)) if n >= r else 0

def probabilityMod(x, y, mod):
    return x * pow(y, mod - 2, mod) % mod

class SortedList:

    def __init__(self, iterable=[], _load=200):
        """"""
        values = sorted(iterable)
        self._len = _len = len(values)
        self._load = _load
        self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
        self._list_lens = [len(_list) for _list in _lists]
        self._mins = [_list[0] for _list in _lists]
        self._fen_tree = []
        self._rebuild = True

    def _fen_build(self):
        """"""
        self._fen_tree[:] = self._list_lens
        _fen_tree = self._fen_tree
        for i in range(len(_fen_tree)):
            if i | i + 1 < len(_fen_tree):
                _fen_tree[i | i + 1] += _fen_tree[i]
        self._rebuild = False

    def _fen_update(self, index, value):
        """"""
        if not self._rebuild:
            _fen_tree = self._fen_tree
            while index < len(_fen_tree):
                _fen_tree[index] += value
                index |= index + 1

    def _fen_query(self, end):
        """"""
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        x = 0
        while end:
            x += _fen_tree[end - 1]
            end &= end - 1
        return x

    def _fen_findkth(self, k):
        """"""
        _list_lens = self._list_lens
        if k < _list_lens[0]:
            return (0, k)
        if k >= self._len - _list_lens[-1]:
            return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        idx = -1
        for d in reversed(range(len(_fen_tree).bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
                idx = right_idx
                k -= _fen_tree[idx]
        return (idx + 1, k)

    def _delete(self, pos, idx):
        """"""
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len -= 1
        self._fen_update(pos, -1)
        del _lists[pos][idx]
        _list_lens[pos] -= 1
        if _list_lens[pos]:
            _mins[pos] = _lists[pos][0]
        else:
            del _lists[pos]
            del _list_lens[pos]
            del _mins[pos]
            self._rebuild = True

    def _loc_left(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (lo, pos) = (-1, len(_lists) - 1)
        while lo + 1 < pos:
            mi = lo + pos >> 1
            if value <= _mins[mi]:
                pos = mi
            else:
                lo = mi
        if pos and value <= _lists[pos - 1][-1]:
            pos -= 1
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value <= _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def _loc_right(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (pos, hi) = (0, len(_lists))
        while pos + 1 < hi:
            mi = pos + hi >> 1
            if value < _mins[mi]:
                hi = mi
            else:
                pos = mi
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value < _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def add(self, value):
        """"""
        _load = self._load
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len += 1
        if _lists:
            (pos, idx) = self._loc_right(value)
            self._fen_update(pos, 1)
            _list = _lists[pos]
            _list.insert(idx, value)
            _list_lens[pos] += 1
            _mins[pos] = _list[0]
            if _load + _load < len(_list):
                _lists.insert(pos + 1, _list[_load:])
                _list_lens.insert(pos + 1, len(_list) - _load)
                _mins.insert(pos + 1, _list[_load])
                _list_lens[pos] = _load
                del _list[_load:]
                self._rebuild = True
        else:
            _lists.append([value])
            _mins.append(value)
            _list_lens.append(1)
            self._rebuild = True

    def discard(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_right(value)
            if idx and _lists[pos][idx - 1] == value:
                self._delete(pos, idx - 1)

    def remove(self, value):
        """"""
        _len = self._len
        self.discard(value)
        if _len == self._len:
            raise ValueError('{0!r} not in list'.format(value))

    def pop(self, index=-1):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        value = self._lists[pos][idx]
        self._delete(pos, idx)
        return value

    def bisect_left(self, value):
        """"""
        (pos, idx) = self._loc_left(value)
        return self._fen_query(pos) + idx

    def bisect_right(self, value):
        """"""
        (pos, idx) = self._loc_right(value)
        return self._fen_query(pos) + idx

    def count(self, value):
        """"""
        return self.bisect_right(value) - self.bisect_left(value)

    def __len__(self):
        """"""
        return self._len

    def __getitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        return self._lists[pos][idx]

    def __delitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        self._delete(pos, idx)

    def __contains__(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_left(value)
            return idx < len(_lists[pos]) and _lists[pos][idx] == value
        return False

    def __iter__(self):
        """"""
        return (value for _list in self._lists for value in _list)

    def __reversed__(self):
        """"""
        return (value for _list in reversed(self._lists) for value in reversed(_list))

    def __repr__(self):
        """"""
        return 'SortedList({0})'.format(list(self))

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 = IOWrapper(sys.stdin)
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))

def getGraph(n, m, directed=False):
    d = [[] for _ in range(n)]
    for _ in range(m):
        (u, v) = LGMI()
        d[u].append(v)
        if not directed:
            d[v].append(u)
    return d

def getWeightedGraph(n, m, directed=False):
    d = [[] for _ in range(n)]
    for _ in range(m):
        (u, v, w) = LII()
        u -= 1
        v -= 1
        d[u].append((v, w))
        if not directed:
            d[v].append((u, w))
    return d
if __name__ == '__main__':
    main()

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
ans = []
for _ in range(t):
    (n, m) = map(int, input().split())
    s = []
    x = [[] for _ in range(26)]
    for i in range(n):
        s0 = list(input().rstrip())
        for j in range(m):
            if s0[j] ^ 46:
                x[s0[j] - 97].append((i + 1, j + 1))
        s.append(s0)
    ans0 = 'YES'
    k = 0
    rc = []
    for l in range(26):
        xl = x[l]
        if len(xl) > max(n, m):
            ans0 = 'NO'
            break
        if not len(xl):
            continue
        k = l + 1
        (sr, sc) = (set(), set())
        for (r, c) in xl:
            sr.add(r)
            sc.add(c)
        if min(len(sr), len(sc)) > 1:
            ans0 = 'NO'
            break
        ok = 1
        if len(sr) == 1:
            (i, mi, ma) = (list(sr)[0] - 1, min(sc) - 1, max(sc))
            (r1, c1, r2, c2) = (i + 1, mi + 1, i + 1, ma)
            for j in range(mi, ma):
                if s[i][j] < l + 97:
                    ok = 0
                    ans0 = 'NO'
                    break
        else:
            (mi, ma, j) = (min(sr) - 1, max(sr), list(sc)[0] - 1)
            (r1, c1, r2, c2) = (mi + 1, j + 1, ma, j + 1)
            for i in range(mi, ma):
                if s[i][j] < l + 97:
                    ok = 0
                    ans0 = 'NO'
                    break
        if ok:
            while len(rc) ^ k:
                rc.append(' '.join(map(str, (r1, c1, r2, c2))))
    ans.append(ans0)
    if ans0 == 'NO':
        continue
    ans.append(str(k))
    if not k:
        continue
    ans.append('\n'.join(rc))
sys.stdout.write('\n'.join(ans))