Минимальное количество сальто для получения соседних единиц в массиве

Question

Учитывая двоичную матрицу (значения 0 или 1), соседние записи 1 обозначают «холмы».Кроме того, учитывая некоторое число k, найдите минимальное число 0, которое вам нужно «перевернуть» на 1, чтобы сформировать холм по крайней мере размера k.

Редактировать: Для пояснениясмежный означает соседство влево-вправо-вверх-вниз.Диагонали не считаются смежными.Например,

[0 1 0 1]

- это один холм размера 2,

[0 1 1 0]

определяет 2 холма размера 1,

[0 1 1 1]

определяет 1 холм размера 3, а

[1 1 1 1]

определяет 1 холм размера 4.

Также дляПояснение: размер определяется областью, образованной смежным BLOB-объектом из 1-х.

Мое первоначальное решение связано с преобразованием каждого существующего холма в узлы графа, а стоимость - минимальный путь друг к другу.узел.Затем, выполняя DFS (или аналогичный алгоритм), чтобы найти минимальную стоимость.

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

Answer 1

Холм состоит из четырех последовательностей 1:

Правильная последовательность состоит из r «битов»последовательность up имеет u битов и т. д.

Холм размера k равен k= 1 + r + l + u + d (1 центральный + последовательности), где каждое значение равно 0 <= v < k.

Проблема комбинаторная .Для каждой ячейки должны быть проверены все возможные комбинации {r,l,u,d}, которые удовлетворяют предыдущему отношению.

При тестировании комбинации в ячейке необходимо подсчитать количество существующих 1 в каждом значениикомбинации они не «переворачивают».Это также пропустит рано некоторые другие комбинации.