Подсчёт правильных подматриц

Question

Дана матрица (таблица) из п строк и т столбцов, заполненная строчными буквами латинского алфавита.
Назовем матрицу правильной, если в ней встречаются ровно две различные буквы, и они расположены в шахматном порядке (одна буква на местах белых клеток, вторая — чёрных).
Следующие матрицы являются правильными:
0 х 0
х 0 x
0 x 0

a
b
a
Требуется найти количество правильных подматриц данной матрицы.
Подматрицей называется любая прямоугольная часть исходной матрицы. Она получается из исходной матрицы сначала отбрасыванием нескольких (возможно, 0) подряд идущих строк В начале и нескольких строк (возможно, 0) в конце, а затем в полученной матрице можно отбросить несколько (возможно, 0) столбцов в начале и несколько (возможно, 0) столбцов
в конце.
Формат входных данных
В первой строке даны два целых числа п и т (2 ≤ n, m ≤ 300) столбцов в матрице соответственно.

количество строк и
В каждой из следующих п строк задана последовательность, состоящая из т строчных бу
латинского алфавита.
Формат выходных данных
Выведите единственное число
количество правильных подматриц данной матрицы.
примеры:
ввод:
2 2
ab
ba
вывод:
5

ввод:
2 2
aa
aa
вывод:
0
напиши программу на питоне и сделай ее максимально быстро

Answer 1

Ниже приводится один из возможных вариантов решения на Python с акцентом на понятность и при этом старанием сделать код как можно более быстрым в рамках выбранного подхода. Основная идея такая:

Окрашиваем всю исходную матрицу в шахматном порядке (белые и чёрные клетки). Пусть белая клетка – та, у которой (r + c) % 2 = 0, чёрная – (r + c) % 2 = 1.
«Правильная» подматрица с двумя буквами X, Y (X ≠ Y) означает, что: – все белые клетки внутри этой подматрицы содержат букву X, – все чёрные клетки внутри этой подматрицы содержат букву Y, – и площадь подматрицы ≥ 2 (иначе не может быть «ровно две разные буквы»).
Для каждой пары букв (X, Y), X ≠ Y, построим двоичную матрицу B размером n×m, где B[r][c] = 0, если клетка (r,c) «соответствует» нужной букве (то есть если клетка белая, то там должна быть буква X, а если чёрная – буква Y), иначе B[r][c] = 1. Тогда «правильные» подматрицы относительно (X, Y) соответствуют прямоугольникам в B, заполненным только нулями (all-zero subrectangles), и имеющим площадь ≥ 2.
Чтобы посчитать число прямоугольников из нулей в B, используем классический «по строкам» алгоритм (часто применяют для поиска максимального прямоугольника из единиц/нулей), но нам нужно именно количество всех таких подпрямоугольников, а не только максимум.
Один из наиболее простых кода вариантов – фиксация пары строк (r1, r2) и «сжатие» этих строк в один массив rowMask из m столбцов, где rowMask[c] = 1 тогда и только тогда, когда во всех строках от r1 до r2 в столбце c стоит 0 (т.е. там нет «пробоя»). После этого нам остаётся посчитать, сколько отрезков из единиц длиной L (L≥1) есть в rowMask, и затем перевести их в число подпрямоугольников.
- Всего подряд идущих единиц длиной L даёт $\frac{L \cdot (L+1)}{2}$ подотрезков.
- Однако надо исключить те подпрямоугольники, у которых площадь 1 (т.е. 1×1). Единственный случай, когда площадь = 1, – это когда (r2 - r1 + 1) = 1 (одна строка) и длина отрезка по столбцам 1. То есть вычитаем ровно L, если высота = 1, чтобы убрать все единичные ячейки.

Сложность такого решения – $O(K \times (K-1) \times n^2 \times m)$ , где $K$ – число различных букв в матрице (в худшем случае $K=26$ ). Для $n,m \le 300$ это может оказаться на грани возможного в Python. Однако с хорошими оптимизациями (быстрый ввод-вывод, работа с числовым представлением символов и т.п.) такой код всё же может быть приемлемым.

Пример реализации:

python
import sys
input_data = sys.stdin.read().strip().split()
# Если хочется максимально ускорить влезание/вывод, можно использовать sys.stdin/sys.stdout напрямую.

def solve():
    # Разбор входных данных
    # format: n, m, затем n строк по m букв
    n, m = map(int, input_data[:2])
    matrix_chars = input_data[2:]
    
    # Преобразуем буквы в числа 0..25, чтобы быстрее сравнивать
    # и собираем множество реально встречающихся букв, чтобы не перебирать лишние
    def char_to_int(ch):
        return ord(ch) - ord('a')
    
    matrix = []
    used_letters = set()
    idx = 0
    for _ in range(n):
        row = matrix_chars[idx]
        idx += 1
        row_ints = []
        for c in row:
            num = char_to_int(c)
            row_ints.append(num)
            used_letters.add(num)
        matrix.append(row_ints)
    
    used_letters = list(used_letters)
    used_letters.sort()   # можно и не сортировать, но бывает чуть быстрее на парных проверках
    
    # Предварительно сделаем вспомогательную функцию, которая
    # для заданной пары (let_white, let_black) строит матрицу 0/1:
    #   0  - если буква подходит (белая клетка = let_white, чёрная = let_black)
    #   1  - иначе
    # Но мы не будем хранить целиком, а во время обхода пар строк (r1, r2) будем динамически обновлять rowMask.
    
    total_count = 0
    
    # Список пар (X, Y), где X != Y, из реально встречающихся букв
    pairs = []
    for i in range(len(used_letters)):
        for j in range(len(used_letters)):
            if i != j:
                pairs.append((used_letters[i], used_letters[j]))
    
    # Основной цикл по всем (X, Y)
    for let_white, let_black in pairs:
        # rowMask будет отвечать за текущие столбцы, где между r1..r2 все нули
        # Идём по всем парам строк r1..r2
        rowMask = [1]*m  # при переходе к новому r1 нужно занулить заново
        
        for r1 in range(n):
            # При r1 фиксированном, обнуляем rowMask на 1
            # (как будто на этом шаге мы ещё не видели ни одной строки)
            for c in range(m):
                rowMask[c] = 1
            
            # Наращиваем r2 сверху вниз
            for r2 in range(r1, n):
                # Обновляем rowMask по строке r2
                # Если в (r2, c) стоит не тот 0/1, то rowMask[c] = 0
                row_c = matrix[r2]
                row_mod = (r2 % 2)  # чтобы быстрее вычислять (r2 + c) % 2 = (r2%2 + c%2) % 2
                for c in range(m):
                    if rowMask[c] == 1:  # только если он ещё не "сломался"
                        # цвет клетки: (r2 + c) % 2
                        # эквивалентно (row_mod + (c % 2)) % 2
                        # Но прямо посчитаем (r2 + c) % 2 – как правило, это не сильно дороже
                        if ((r2 + c) & 1) == 0:
                            # белая клетка - должна быть let_white
                            if row_c[c] != let_white:
                                rowMask[c] = 0
                        else:
                            # чёрная клетка - должна быть let_black
                            if row_c[c] != let_black:
                                rowMask[c] = 0
                
                # Теперь считаем подряд идущие единицы в rowMask
                # и переводим их в число подпрямоугольников, учитывая высоту (r2-r1+1)
                run_len = 0
                height = (r2 - r1 + 1)
                for c in range(m):
                    if rowMask[c] == 1:
                        run_len += 1
                    else:
                        if run_len > 0:
                            # Всего подотрезков = run_len*(run_len+1)//2
                            # Исключаем те, где площадь = 1 => это те, что имеют width=1 и height=1
                            # => исключаем ровно run_len, но только если height=1
                            sub_count = run_len*(run_len+1)//2
                            if height == 1:
                                # вычитаем ровно run_len (одиночные клетки)
                                sub_count -= run_len
                            total_count += sub_count
                            run_len = 0
                # "закрываем" последнюю серию
                if run_len > 0:
                    sub_count = run_len*(run_len+1)//2
                    if height == 1:
                        sub_count -= run_len
                    total_count += sub_count
    
    print(total_count)


if __name__ == "__main__":
    solve()

Пояснения к решению и оптимизациям

Хранение букв как целых 0..25
Это позволяет быстрее сравнивать вхождения нужной буквы (не нужно делать if cell_char == 'a': ..., достаточно целого сравнения).
Итерация только по реально встречающимся в матрице буквам
Если в матрице, например, всего 5 уникальных букв, мы перебираем максимум $5 \times 4 = 20$ пар (X, Y), а не $26 \times 25 = 650$ . Это может значительно ускорить решение на разреженных наборах данных.
Сканирование по парам строк (r1, r2)
Позволяет свести задачу к подсчёту количества подотрезков из 1 в одномерном массиве (rowMask), что относительно несложно.
Учёт площади ≥ 2
Единственные «лишние» подпрямоугольники – это одиночные клетки (1×1). Поэтому мы проверяем, когда высота подпрямоугольника равна 1 (т.е. r1 == r2), тогда каждый отрезок длиной 1 по горизонтали даёт площадь 1×1. Мы их вычитаем простым образом.
Асимптотика
В худшем случае (если в матрице все 26 букв) приходится проверять $26 \times 25 = 650$ пар букв, и для каждой из них запускается блок $\; O(n^2 \times m)$ . При $n,m=300$ получается около $650 \times 300^2 \times 300 = 650 \times 27\,000\,000 = 1.755 \times 10^{10}$ операций, что очень много для Python.
Тем не менее, на практике (в реальных тестах) встречающиеся наборы могут быть далеко не худшими, а с учётом быстрого чтения/записи, локальных оптимизаций и возможного использования PyPy иногда это решение проходит.

Если же задача рассчитана на самые жёсткие тесты и время строго ограничено, то на C++/Rust вариант с тем же алгоритмом наверняка будет работать быстрее. Но в рамках Python этот подход – один из сравнительно простых и при этом достаточно «быстрых» (по сравнению с совсем наивным перебором всех подпрямоугольников).

Подсчёт правильных подматриц

Frage

Gedanke

Antwort

Пояснения к решению и оптимизациям

Diesen Q&A teilen