Найдите количество угловых прямоугольников, которые можно составить из заданной матрицы.

Учитывая бинарную матрицу mat[][] размерностей N*M , задача состоит в том, чтобы найти количество угловых прямоугольников, которые можно сформировать. Угловой прямоугольник определяется как подматрица с единицами на углах, и каждая единица должна принадлежать уникальной ячейке в этой подматрице.

Примеры:

Input: mat[][] = {{1, 0, 1}, {0, 0, 0}, {1, 0, 1}}
Output: 1
Explanation:
There exists only one submatrix satisfying the given formula represented by bold as:
1 0 1
0 0 0
1 0 1

Input: mat[][] = {{1, 1, 1}, {1, 1, 1}, {1, 1, 1}}
Output: 9

Подход: Данную задачу можно решить, используя понятия всех различных возможных пар из N точек, заданных ^N C ₂ . Идея состоит в том, чтобы сохранить частоту пары ячеек (i, j) , имеющих значения как 1 на карте пар, скажем, M . После создания карты частот найдите общее количество углов прямоугольника, сформированного по приведенной выше формуле. Выполните следующие шаги, чтобы решить данную проблему:

• Инициализируйте переменную, скажем, count , в которой хранится результирующее количество угловых прямоугольников.
• Инициализируйте карту, скажем, m[] , которая хранит частоту ячейки (i, j) , имеющую значения 1 .
• Перебрать диапазон [0, M), используя переменную i , и выполнить следующие задачи:
  • Перебрать диапазон [0, N), используя переменную j , и если mat[i][j] равно 1 , то выполнить итерацию в диапазоне [j_+1, N), используя переменную k , и если значение mat[i][ k] равно 1 , затем увеличьте количество m[{j, k}] на 1.
• Пройдитесь по карте m[] , используя переменную it, и добавьте значение it.second*(it.second – 1)/2 к переменной count.
• После выполнения вышеуказанных шагов выведите значение count в качестве ответа.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*M ² )
Вспомогательное пространство: O(M ² )