Seen verbinden

Ben04

Hallo,

ich hab hier eine Problemstellung bei der ich nicht weis wie ich sie lösen soll. Es geht darum eine Reihe von Seen mit Kanälen zu verbinden. Als Eingabe gibt es ein 2D Array, in etwa wie folgt

Alle zusammenhängende 1sen bilden einen See. So nun soll man alle Seen verbinden und dabei möglichst wenige Kanäle graben. Man darf überall wo eine 0 ist ein Kanal graben und 2 Seen gelten als verbunden wenn man sich horizental oder vertikal über Seen und Kanäle von einem See zum anderen bewegen kann.

Es kann mehere Lösungen geben. Beispiel:

aber auch

haben jedesmal eine Kanallänge von 5. Gefragt ist allerdings nur die minimale Kanallänge, also bei diesem Beispiel 5, und nicht die genauen Positionen der Kanäle.

Ich bin für jede Hilfe dankbar.

phlox81

Hm, als erstes würde ich mir eine Struktur für die seen machen,
die jeweils einen see abbilden:

struct pos
{
int x,y;
}
class see
{
  std::set<pos> positionen;
}

Dann musst du halt noch jeweils dein array durchgehen,
und feststellen ob die 1 die du gefunden hast, schon zu einem
See gehört, wenn nein -> neuen See erstellen, und alle angrenzenden
1 solange eintragen, bis er erfasst ist.

Dann musst du nur noch für jeden See zu jedem Nachbar see
die kürzeste Verbindung herausfinden...

Devil

TomasRiker

Und achte auf Folgendes: Wenn Du zwei Seen verbunden hast, musst Du sie "verschmelzen", also sie nur noch wie einen einzigen See behandeln, zu dem auch die Verbindungsfelder gehören. Dann kann's nämlich auch "Wegkreuzungen" geben.
Es gab mal einen PHP-Coding-Contest, in dem fast genau diese Aufgabe gestellt wurde. Man konnte nachher auch die Codes der Teilnehmer runterladen.

Ben04

Mir ist noch nicht klar wie ich das angehen soll. Wie ich die einzeln 1sen zu einem See zusammen fügen kann ist mir klar, wie ich den kürzesten Weg zwischen 2 Seen suche auch, allerdings danach stehe ich auf dem Schlauch.

Was mir auch nicht klar ist wie ich den Weg zwischen einem See und einem "verschmelzten" See suchen soll. Es ist ja gut möglich, dass es mehrere gleiche gute Möglichkeiten gibt 2 Seen zu verschmelzen welche allerdings unterschiedlich abschneiden können wenn ich den Weg suche.

EDIT: Ich hab ein paar Rechtschreibfehler verbessert.

volkard

devil81 schrieb:

Dann musst du nur noch für jeden See zu jedem Nachbar see
die kürzeste Verbindung herausfinden...
Devil

glaub ich nicht.

das würde ja aus

* *

* *

sowas

*-*
|X|
*-*

machen. dabei reicht

*-*
|
*-*

wenn man von jedem see zu jedem anderen weiß, wieviele löcher man für diese verbindung buddeln müßte, könnte man fast versuchen, unter "minimaler spannbaum" oder so einen algo im netz zu suchen.

ist aber nicht so einfach, weil sobald ein kanal zwischen zwei seen geschaufelt wurde, alle anderen kanalkosten betroffen sein könnten.

mir fällt im moment nix besseres als bruteforcen ein, um ganz sicher zu gehen.

phlox81

volkard schrieb:

devil81 schrieb:

Dann musst du nur noch für jeden See zu jedem Nachbar see
die kürzeste Verbindung herausfinden...
Devil

glaub ich nicht.

das würde ja aus
* *

* *
sowas
*-*
|X|
*-*
machen. dabei reicht
*-*
|
*-*
wenn man von jedem see zu jedem anderen weiß, wieviele löcher man für diese verbindung buddeln müßte, könnte man fast versuchen, unter "minimaler spannbaum" oder so einen algo im netz zu suchen.

ist aber nicht so einfach, weil sobald ein kanal zwischen zwei seen geschaufelt wurde, alle anderen kanalkosten betroffen sein könnten.

mir fällt im moment nix besseres als bruteforcen ein, um ganz sicher zu gehen.

Ich wollte nur nicht weiter ins Detail gehen.
Natürlich würde man dann die kürzeste wegstrecke mit allen seen drin suchen müssen.

Devil

TomasRiker

volkard schrieb:

dabei reicht
*-*
|
*-*

Reichen würde sogar schon

* *
 X
* *

Ben04

Das geht nicht da Kanäle nur horizental oder vertikal sein dürfen.

TomasRiker

Achso, dann wirst Du mit den Einsendungen vom PHP-Contest wohl leider doch nicht so viel anfangen können.