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

У меня есть двумерный массив размера 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]. У меня проблемы с реализацией этого, так как я не знаю, как пройти все подмассивы для данного индекса. Я пытаюсь это так долго, но все еще не достиг этого. Кто-нибудь может помочь?


c++ arrays loops dynamic-programming sub-array
person Ayaz S Imran    schedule 13.10.2018    source источник
comment
Используйте вектор векторов или массив массивов и два цикла на основе диапазона. Или реализуйте свой собственный матричный класс.   -  person Ron    schedule 13.10.2018
comment
@ Рон Можешь объяснить?   -  person Ayaz S Imran    schedule 13.10.2018
comment
Просто чтобы было ясно, алгоритм динамического программирования здесь не вопрос, верно?   -  person Davis Herring    schedule 14.10.2018
comment
@ Дэвис, вот в чем вопрос   -  person Ayaz S Imran    schedule 14.10.2018

Ответы (1)


arrow_upward
0
arrow_downward

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

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

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

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

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

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

person Davis Herring    schedule 14.10.2018