witzeforum.de

Hi,

vielleicht kennt einer das Rätsel vom Adventskalender, aber egal

es geht darum, dass ihr ein 8*8 großes Feld habt.

auf jedem feld ist ein haus.

ihr sollt jetzt stege von feld zu feld bauen, sodass der abstand zwischen 2 benachbarten(nicht diagonalen) feldern insgesamt minimal ist.

zur verdeutlichung:


X-X
| |
X X

alle häuser haben den abstand 1, nur die beiden häuser unten den abstand 3.

achja, es gibt natürlich ne einschränkung^^

es darf kein gebiet innerhalb des feldes komplett von stegen umschlossen werden.

mein rekord für ein 8*8 feld liegt bei 296, mal schauen, ob das wer unterbietet!

also ehrlich gesagt versteh ich die Aufgabenstellung nicht so ganz....

Also nun mal langsam.... was soll ich machen??

ok^^ war wohl doch ein wenig schnell formuliert


ihr habt 64 felder. zwischen diesen feldern sollt ihr horizontal und vertikal stege legen.


X-X das - ist ein horizontaler steg

Die beiden Häuser haben den Abstand 1

Y-X-X-X-Y

Die beiden Y haben den Abstand 4

X-X
| |
Y Y

Y haben hier Abstand 3(über die Stege)

jetzt sollt ihr so stege legen in dem 8*8-Feld, dass alle Abstände addiert möglichst gering werden.

dabei darf niemals sowas entstehen:

X-X-X
|___|
X-X-X

Also kein gebiet, das völlig umschlossen ist...

so ich hoffe, es ist deutlicher geworden^^

OK aus dem was ich verstandne habe geht das hervor:

X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X
X X X X X X X X


Aber unen sind doch 8 Häuser. Kannst du mir mal sagen woher du das hast oder ein Bild dazu geben oderso? ich glaub ich bin zu dämlich dafür

ah fuck, hab was wichtiges vergessen


der abstand gilt nur zwischen 2 direkt benachbarten feldern!!!!


also ein beispiel:


X-X-X
|
X-X-X
____|
X-X-X

X-X-X
__|
X-X-X
__|
X-X-X


Die _ sind nur dafür da, dass die | richtig erscheinen, da das forum das sonst nicht macht^^

beim oberen beispiel haben die beiden häuser ganz oben rechts und einen darunter den abstand 5(den stegen folgend)

insgesamt addieren sich alle abstände im oberen beispiel zu 24(2*5+2*3+8*1), im beispiel unten nur zu 20(4*3+8*1), also ist die untere struktur besser.

baut einfach mal ein wenig drauf los, dann werdet ihr schnell sehen, was gut ist und was nicht^^

Die gesuchte Lösung ist ein minimaler Steinerbaum in einem 8x8 Gitter.

Ich denke mal, das eines der vier felder in der mitte der zentrale knoten des Steinerbaums ist.
Dann sollte eine Breitensuche die beste Lösung liefern.

888xuerong-4:
Cheap Uggs UK