алгоритм поиска всех подматриц и проверка их прямоугольности

Докажем, что наличие пересекающихся красивых подтаблиц равносильно тому, что в исходной таблице есть квадрат 2×2 с тремя чёрными и одной белой ячейкой.

Пусть А и Б - две разные красивые таблицы, которые пересекаются, М - общая ячейка А и Б. В строке, содержащей М, выберем ячейки, входящие в А или Б. В этой выборке есть хотя бы одна ячейка, которая принадлежит ровно одной из таблиц А или Б (если это не так, то А и Б совпадают по горизонтальным координатам, а значит их объединение будет чёрным прямоугольником, содержащим А и Б, что противоречит условию, что в любой подтаблице, которая содержит в себе "красивую", есть хотя бы одна белая ячейка).

Пусть Н - ячейка в строке с М, принадлежащая ровно одной таблице. Поскольку ячейка М общая для А и Б, то она находится в той же таблице, что и Н, вместе с соединяющим их отрезком. То есть, отрезок МН состоит из черных ячеек. А поскольку Н принадлежит ровно одной таблице, а М - двум, то отрезок МН пересекается с ребром другой таблицы. Построим на этом ребре новый прямоугольник (подтаблицу), так чтобы сторона, параллельная этому ребру, проходила через ячейку Н:

В этом прямоугольнике будет хотя бы одна белая ячейка (если это не так, то он мог бы расширить таблицу, на ребре которой построен, до нового чёрного прямоугольника, что противоречит упомянутому условию: в таблице содержащей "красивую", должна быть белая ячейка). Выберем среди этих белых ячеек те, которые находятся ближе всего к отрезку МН, а из них выберем ближайшие к опорному ребру. В результате мы получим одну или две (симметричные относительно МН) ячейки, которые, согласно построению и тому факту, что опорное ребро и отрезок МН состоят из черных ячеек, будут окружены на углу, направленном в сторону М, тремя черными ячейками. А значит, если две подтаблицы пересекаются, то исходная таблица содержит квадрат 2×2 с тремя чёрными ячейками и одной белой.

Верно и обратное. Если исходная таблица содержит квадрат 2×2 с тремя чёрными ячейками и одной белой, то мы можем разбить три черные на две пары с одной общей ячейкой. Каждую пару продлим в оба конца, выбрав самые длинные черные отрезки. По одну из сторон этих отрезков находится белая ячейка. Следовательно они будут ребрами двух красивых подтаблиц, которые не равны друг другу, но пересекаются как минимум в общей для двух исходных пар ячейке.

Исходя из этого алгоритм поиска ответа сводится к поиску квадрата размером 2×2, сумма ячеек которого равна 3. Если такого квадрата нет, то пересекающихся красивых подтаблиц нет.

Пример на Python:

def no_intersections(table: list[list[int]]) -> Literal['yes', 'no']:
    ''' Вернуть 'yes', если "красивые" подтаблицы из table 
    попарно не пересекаются. В противном случае вернуть 'no'.
    '''
    max_height = len(table) - 1
    max_width = len(table[0]) - 1 
    for x in range(max_height):
        for y in range(max_width):
            total = table[x][y] + table[x+1][y] + table[x][y+1] + table[x+1][y+1]
            if total == 3:
                return 'no'
    return 'yes'

---

P.S. Код для экспериментов:

from io import StringIO
from typing import Literal

def no_intersections(table: list[list[int]]) -> Literal['yes', 'no']:
    max_height = len(table) - 1
    max_width = len(table[0]) - 1 
    for x in range(max_height):
        for y in range(max_width):
            total = table[x][y] + table[x+1][y] + table[x][y+1] + table[x+1][y+1]
            if total == 3:
                return 'no'
    return 'yes'

data = '''\
5
4 5 no
11111
00100
00100
00100
5 5 yes
11011
11011
11000
11011
11011
5 4 no
1111
1001
1111
1001
1001
4 4 no
1001
1101
1011
1001
5 4 no
1001
1010
1100
1010
1001
'''

test_tables = []
with StringIO(data) as file:
    n = int(file.readline().strip())
    for _ in range(n):
        row, col, answer = file.readline().split()
        row = int(row)
        col = int(col)        
        table = [list(map(int, record[:col])) for _, record in zip(range(row), file)]
        test_tables.append((table, answer))

for case_index, (table, expected) in enumerate(test_tables, 1):
    output = no_intersections(table)
    test_result = 'PASSED' if expected == output else 'FAILED'
    print('Case: %d\tExpected: %3s\tOuput: %3s\t%s' % (case_index, expected, output, test_result))

Case: 1 Expected:  no   Ouput:  no  PASSED
Case: 2 Expected: yes   Ouput: yes  PASSED
Case: 3 Expected:  no   Ouput:  no  PASSED
Case: 4 Expected:  no   Ouput:  no  PASSED
Case: 5 Expected:  no   Ouput:  no  PASSED