Es gibt ein Raster der GrößeN x M. Einige Zellen sind Inseln bezeichnet mit '0' und die anderen sindWasse. Auf jeder Wasserzelle befindet sich eine Nummer, die die Kosten einer Brücke angibt, die auf dieser Zelle hergestellt wurde. Sie müssen die Mindestkosten ermitteln, für die alle Inseln verbunden werden können. Eine Zelle ist mit einer anderen Zelle verbunden, wenn sie eine Kante oder einen Scheitelpunkt teilt.

Welcher Algorithmus kann zur Lösung dieses Problems verwendet werden?
Bearbeiten Was kann als Brute-Force-Ansatz verwendet werden, wenn die Werte von N, M sehr klein sind, z. B. NxM <= 100?

Beispie: In dem angegebenen Bild geben grüne Zellen Inseln an, blaue Zellen Wasser und hellblaue Zellen die Zellen, auf denen eine Brücke gebaut werden soll. Für das folgende Bild lautet die Antwort also 17.

m Anfang dachte ich daran, alle Inseln als Knoten zu markieren und jedes Inselpaar durch eine kürzeste Brücke zu verbinden. Dann könnte das Problem auf Minimum Spanning Tree reduziert werden, aber bei diesem Ansatz habe ich den Fall übersehen, in dem sich Kanten überlappen.Beispielsweis, in der folgenden Abbildung ist der kürzeste Abstand zwischen zwei Inseln7 (gelb markiert). Wenn Sie also Minimum Spanning Trees verwenden, lautet die Antwort 14, aber die Antwort sollte @ se 11 (hellblau markiert).