Informatiker Board | Theoretische Informatik | Flood-Fill-Algorithmus in Python

Informatiker Board » Themengebiete » Theoretische Informatik » Flood-Fill-Algorithmus in Python

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Flood-Fill-Algorithmus in Python

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Nerdy
unregistriert

Flood-Fill-Algorithmus in Python

Zitatantwort auf diesen Beitrag erstellen

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

07.05.2016 21:52

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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.

__________________
Syntax Highlighting fürs Board (Link)

08.05.2016 07:14

Nehmen Sie eulerscheZahl in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Flood-Fill-Algorithmus in Python