Informatika gyűjtemény

NézetNyomtat

Sakk (Megoldás)
Címkék > Feladat
Elmélet > Algoritmusok > Gráfalgoritmusok
Versenyek > Nemes Tihamér OKSzTV > 2009 > Második forduló > 11-13. osztály

Algoritmus

Nagyon egyszerű a képlet: az adott pozíció minden "szomszédját" (lóugrásban értve) meglátogatjuk és ha ott nem jártunk, akkor beírjuk a lépés számot, majd ugyanígy ezek szomszédjait is megnézzük (szélességi bejárás). Csak akkor kell beírni ha ott még nem jártunk, hiszen egy adott pillanatban mindenhol a minimum lépésszám van, tehát soha sem lehet olyan, hogy egy későbbi időpillanatban kiderül, hogy az adott mező kevesebb lépéssel is elérhető.

Megoldások

Kriván Bálint (C#): kb_sakk.cs