Nicht erreichbare Abschnitte einer 2D-Karte finden

Question

Ich möchte nicht, dass Sie dieses Problem für mich lösen, ich möchte nur nach einigen Ideen fragen.

Dies ist die Eingabe unten, und es stellt eine Karte dar. Das 'x' steht für Land und die Punkte - Wasser. Mit dem 'x' können Sie also 'Inseln' auf der Karte darstellen.

xxx.x...xxxxx   
xxxx....x...x   
........x.x.x   
..xxxxx.x...x  
..x...x.xxx.x   
..x.x.x...x..   
..x...x...xxx   
...xxxxxx....   
x............ 

Wie Sie sehen können, gibt es einige Inseln, die geschlossen sind, dh wenn einige Boote in seinem Gebiet ist, wird es nicht in der Lage sein, um aus, für die Ex:

..xxxxx.  
..x...x.   
..x.x.x.   
..x...x. 
..xxxxx. 

Und gibt es einige offene Inseln, die möglich ist, aus ihnen heraus zu bekommen, ab:

.xxxxx   
.x...x   
.x.x.x   
.xxx.x  

Das Problem ist folgendes: Für eine gegebene NxM Karte wie die oben berechnen howm jede der Inseln sind offen, und wie viele geschlossen.

Ich wiederhole: Ich möchte nicht, dass Sie es lösen, brauchen nur einige Anregungen, Ideen zum Lösen. danke

Answer 1

Ich denke, dass die Verwendung des guten alten Flutfüllungsalgorithmus Ihnen sagen sollte, wenn Sie von irgendeinem Punkt einen anderen Punkt erreichen können.

http://en.wikipedia.org/wiki/Flood_fill

Auch können Sie besser definieren müssen, was Sie von innen und außen bedeuten (glaube ich).

Answer 2

Machen Sie einfach einen verbundenen Graphen von allen Punkten (markieren Sie sie während der Verbindung) und wenn Sie fertig sind - prüfen Sie, ob einer der Graphknoten im Umkreis ist. dann weiter zum nächsten unmarkierten Punkt.

Es gibt einige allgemeine bekannte Algorithmen einen zusammenhängenden Graphen erstellen ....

Answer 3

Sie es in eine Matrix lesen können, und suchen Sie nach. oder x, und wenn Sie eine finden. oder x, führe eine rekursive Funktion aus, die nach benachbarten Verbindungen sucht. Wenn Sie fertig sind, suchen Sie nach dem nächsten. oder x das noch nicht analysiert wurde und wiederholen.

Answer 4

Ich gehe davon aus, dass Sie mit "nahe" eine Insel meinen, die mindestens ein Quadrat des Meeres enthält, von dem aus man nicht an die Grenzen der Karte gelangen kann; und mit "offen" meinst du jede andere Insel da draußen.

So entdecken Sie zuerst, welche Meereskacheln von den Grenzen der Karte aus erreichbar sind - indem Sie von jeder Meeresfliese an der Grenze eine Flutfüllung verwenden und diejenigen markieren, die Sie passieren. Wenn am Rand noch Seeziegel vorhanden sind, fahren Sie mit der Flutfüllung von dort fort.

Nachdem Sie nun alle von der Grenze erreichbaren Kacheln markiert haben, sind alle anderen Kacheln von Land eingeschlossen. Sie können für jedes von denen die Insel finden, die es einschließt (indem Sie sagen, dass Sie nach Norden gehen, um Land zu entdecken), und verwenden Sie Flutfüllung auf den Landfliesen, um die Landfliesen der Insel zu markieren.

Auf diese Weise können Sie Inseln zählen, die Meeresfliesen einschließen - "geschlossene" Inseln.

Jedes unmarkierte Landplättchen gehört zu einer "offenen" Insel. Verwenden Sie die Flutfüllung erneut, um diese zu zählen.

Answer 5

Hier sind einige einfache Kennzeichnungsvorschriften:

• Wasser ist entweder öffnen oder schließen
• Edge ist offenes Wasser
• nächsten Wasser Wasser offen ist

Answer 6

Flooding-Algorithmus zu öffnen, oder BFS