Есть сетка размераН х М, Некоторые клеткиострова обозначается как «0», а остальныеводы, Каждая водяная ячейка имеет номер, обозначающий стоимость моста, сделанного в этой ячейке. Вы должны найти минимальную стоимость, к которой могут быть подключены все острова. Ячейка связана с другой ячейкой, если она имеет общее ребро или вершину.

Какой алгоритм можно использовать для решения этой проблемы?
Редактировать: Что можно использовать в качестве метода грубой силы, если значения N, M очень малы, скажем, NxM <= 100?

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

Сначала я думал о том, чтобы пометить все острова как узлы и соединить каждую пару островов самым коротким мостом. Тогда проблема может быть сведена к минимальному остовному дереву, но в этом подходе я пропустил случай, когда ребра перекрываются.НапримерНа следующем рисунке кратчайшее расстояние между любыми двумя островками7(отмечено желтым цветом), поэтому с помощью Minimum Spanning Trees ответ будет14, но ответ должен быть11 (отмечено голубым цветом).