Flood-Fill-Algorithmus in Python

07.05.2016, 21:52

Nerdy

Flood-Fill-Algorithmus in Python

Meine Frage:
Hallo, ich bin neu hier und studiere Ingnieurinformatik im zweiten Semester.Zurzeit beschäftige wir uns mit Python und müssen einige Sachen zu Hause implementieren. Mir fällt leider ein Ansatz zur folgenden Aufgabe:

Schreiben Sie eine Flood-Fill-Algorithmus, der ein umrandetes Spielfeld mit Zeichen ausfüllt. Das Spielfeld wird als Liste erzeugt. Die Liste enthält als Elemente wiederum Zeilen-Listen.

Das Spielfeld hat z.B. die Größe numberOfColumns=20 und numberOfRows=10 und enthält in Zeile 1 und 8 und in Spalte 3 und 15 ?x?e als Spielfeldumrandung.

?Verwenden Sie emptyMarker = " " und filledMarker = "x?
?Erzeugen Sie das leer Spielfeld field in der angegebenen Größe
?Erzeugen Sie die Spielfeldgrenzen in field indem Sie wie oben angegeben filledMarker einfügen.
?Schreiben Sie eine Funktion printField, der das Spielfeld field übergeben werden kann und die dann das Spielfeld mittels print-Anweisungen ausgibt.

Tipp: Bauen Sie am besten aus der Liste von Strings einen zusammenhängenden String auf, der dann am Ende der Methode ausgegeben wird, um die Darstellung zu vereinfachen.

?Es wird eine Liste von Startpunkten im Spielfeld vorgegeben (z.B. startPoints=[(5,5),(5,10)]) von wo aus der Fill-Algorithmus starten soll. Das Spielfeld soll bis zu den Grenzmarkierungen aufgefüllt werden.
?Überlegen Sie sich den Füllalgorithmus, um Spielfeldbegrenzungen mit beliebiger Form (Kreis, Herzform oder so) zu füllen und implementieren Sie ihn. Geben Sie in jeder Iteration das Spielfeld mit der printField-Funktion aus.

Meine Ideen:
emptyMarker = " "
filledMarker = "x"
field=[
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20],
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20],
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20],
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20],
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20],
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20],
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20],
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20],
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20],
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]]

field=[list(range(0,20))]
for i in range (0,10)
for j in range (0,20)
field [i][j] = emptyMarker

08.05.2016, 07:14

Auf diesen Beitrag antworten »

eulerscheZahl

Es fängt ja schon vorher bei der Initialisierung an: was, wenn die Breite nicht 20, sondern 200 ist? Schreibst du dann auch 200 Zahlen?

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

def printField(field):
	for y in range(len(field)):
		print ''.join([field[y][x] for x in range(len(field[y]))])

emptyMarker = " "
filledMarker = "x"
numberOfColumns = 20
numberOfRows = 10
field = [[emptyMarker for x in range(numberOfColumns)] for y in range(numberOfRows)]
for x in range(numberOfColumns):
	field[1][x] = filledMarker
	field[8][x] = filledMarker
for y in range(numberOfRows):
	field[y][3] = filledMarker
	field[y][15] = filledMarker
printField(field)

Beim Füllen würde ich so vorgehen:
1. Markiere die Punkte
2. Finde alle Nachbarn, die noch nicht markiert sind
3. Wenn die Nachbarnliste nicht leer ist, mache bei 1. weiter.

Neue Frage »

Antworten »

Flood-Fill-Algorithmus in Python

Verwandte Themen