Обход всех подмассивов двумерного массива

Question

У меня есть двумерный массив заданного размера P * Q, и я должен ответить на K вопросов на основе этого массива.Заданный двумерный массив состоит из чисел 0 и 1. Для каждого вопроса мы должны подсчитать максимальный размер любого квадратного подмассива, в котором нет двух одинаковых элементов.Например, если P = Q = 8 и наш заданный массив будет

00101010
00010101
10101010
01010101
10101010
01010101
10101010
01010101

, тогда вопрос Ki позволяет нам выполнить число щелчков Ki (от 0 до 1 или от 1 до 0).

Here K=4(number of questions)
1 2 0 10001
Output: 7 8 6 8

Я понял, что для K1 = 1 мы можем изменить значение индекса массива (1,1) на 1 и получить действительную матрицу размером 7 * 7, на выходе будет 7. Если Ki> = 2наш ответ будет 8. Что я думаю, что мы должны поддерживать массив ans [k], в котором хранится максимальный размер квадратной подматрицы, которая является действительной.Для этого мы можем запустить каждый индекс исходного массива и пройти через его подмассивы и посчитать значение максимального размера для flip = i, если мы начнем с этого индекса.Мы должны сделать это для подмассивов, начиная с каждого индекса, а затем сохранить максимум из них в flip [i].У меня проблемы с реализацией этого, так как я не знаю, как пройти все подмассивы для данного индекса.Я пытаюсь это так долго, но все еще не достигаю этого.Может кто-нибудь помочь, пожалуйста?

Answer 1

Это помогает упростить задачу, чтобы зависеть только от отдельных значений (а не пар соседних значений).Так что XOR сетка с каждой идеальной шахматной доской :

01111111  10000000
10111111  01000000
11111111  00000000
11111111  00000000
11111111  00000000
11111111  00000000
11111111  00000000
11111111  00000000

, где теперь цель найти самый большой квадрат в сетке либо , котораяимеет не более K_i 0s (очевидно, в пользу левого здесь).

Начните с K_i = 0.Чтобы найти наибольший квадрат из 1 с, вычислите для каждой ячейки число 1 в строке и столбце , начиная с него (0 для ячейки, содержащейа 0);самый большой квадрат с этой ячейкой в ​​качестве ее верхнего левого угла (при условии, что это 1) будет тогда на единицу больше, чем минимум длины строки его правого соседа, длины столбцаего нижний сосед и квадратный размер его нижнего правого соседа.(Все это 0 для несуществующих ячеек вне сетки.) Посетите ячейки в diagonal-major , чтобы получить эти значения, когда они вам нужны;обратите внимание на наибольший размер квадрата.

Чтобы обобщить до K_i > 0, сохраните для каждой ячейки эти три значения (длину строки, длину столбца и размер квадрата) для каждого числасальто до K_i .Ячейка с 1 добавляет 1 к каждой длине строки / столбца, как и раньше, в то время как ячейка с 0 сдвигает этих длин до следующего числа бросков, отбрасывает тех, чье количество бросков теперьслишком большое и добавление новое значение 0 для 0 сальто.Для каждой комбинации длины строки на восток, длины столбца на юг и размера квадрата на юго-восток, каждая из которых имеет счетчик отражений, ячейка получает кандидата квадратного размера, который является их минимумом с сумма их числа бросков, плюс один , если ячейка сама по себе равна 0.Для каждого числа бросков (которое не слишком велико) сохраняйте наибольший размер квадрата, отмечая, является ли он наибольшим за все время (для этого числа бросков).

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