Há uma grade de tamanhoN x M. Algumas células sãoilhas denotado por '0' e os outros sãoágua. Cada célula de água possui um número indicando o custo de uma ponte feita nessa célula. Você precisa encontrar o custo mínimo pelo qual todas as ilhas podem ser conectadas. Uma célula é conectada a outra célula se compartilhar uma aresta ou um vértice.

Qual algoritmo pode ser usado para resolver esse problema?
Editar: O que pode ser usado como uma abordagem de força bruta se os valores de N, M forem muito pequenos, digamos NxM <= 100?

Exemplo: Na imagem fornecida, as células verdes indicam ilhas, as células azuis indicam água e as células azuis claras indicam as células nas quais uma ponte deve ser feita. Assim, para a imagem a seguir, a resposta será17.

Inicialmente, pensei em marcar todas as ilhas como nós e conectar cada par de ilhas por uma ponte mais curta. Em seguida, o problema poderia ser reduzido para Árvore de abrangência mínima, mas nessa abordagem, perdi o caso em que as arestas estão sobrepostas.Por exemplo, na imagem a seguir, a menor distância entre duas ilhas é7(marcado em amarelo), portanto, usando Árvores de abrangência mínima, a resposta seria14, mas a resposta deve ser11 (marcado em azul claro).