Под. субматриц с заданными ограничениями из матрицы?

Question

Это вопрос, заданный в одном собеседовании. Я хотел бы знать оптимальный алгоритм получения желаемых результатов. Вопрос: Учитывая, что у вас есть (n x m) матрица с некоторыми номерами в ней. Теперь вы должны посчитать не матриц размера> = (2 х 2), который будет иметь следующие два условия:

• Он должен иметь по крайней мере два-1-х;
• Два из угловых элементов матрицы равны.

Я знаю алгоритм грубой силы для взятия всех элементов матрицы 2 x 2 и более; затем подсчитывая нет. 1 и проверять 6 возможных условий угловых элементов, причем любые два из них равны. Я хочу знать способ решения этих проблем или любого источника, поскольку я ничего не мог найти на «GeeksForGeeks» или StackOverFlow сам по себе наиболее оптимизирован.

Answer 1

Это подсказка к оптимальному пути.

Во-первых построить (п, т) матрицу, которая подсчитывает количество 1 в (1-я, 1-J) подматрица: п м операций, п м памяти

Теперь для каждого элемента матрица, поиск всех элементов после того, как из ниже, равные

• если на ту же строку, вы можете использовать любую строку ниже, чтобы иметь матрицу с 2 углов равны
• если на тот же колонок, вы можете использовать любой столбец после того, как матрица с двумя углами равна
• Если ни на одном и том же ряду, ни на одном столбце у вас ровно одна матрица с двумя углами равна
• Разница элементов крайних углов эквивалентной матрицы предварительно вычисленного числа - это число единиц в подматрице
• как только один подматрицы имеет более чем 2 из них в нем все подматрицы, в том числе и он также будет иметь: вы можете использовать его для короткого замыкания полного анализа

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