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

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

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 2 Beiträge

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.

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