„Nu sta acolo, și apoi se taie în jos un cal.“ (C) Această glumă bărbos și imaginile corespunzătoare găsite pe internet, nu ar putea fi mai bine descrie starea mea chiar acum. Dar asta e un cal nu am tăiat și aruncat;) Totul a început cu o foarte simplu, există lucruri care nu sau gândit niciodată. Deci, în timp ce navigarea pe internet am dat peste această întrebare: „cal de Șah începe traseul său în colțul din stânga jos al plăcii, și îl completează în sus dreapta uglu.Mozhet dacă calul în același timp, pentru a vizita toate domeniile consiliului la un moment dat?“
Întrebarea este cu adevărat pentru copii. tabla de sah (8x8) este format din 64 de celule, celulele din unul dintre cal avem este în valoare, prin urmare, pentru a obține în jurul valorii de toate celulele trebuie sa faca cal 63 accident vascular cerebral. De fiecare dată când se modifică culoarea în timpul celulei, de exemplu, în picioare pe salt negru - vom ajunge pe alb. Celulele din colțul din stânga sus al plăcii și în dreapta jos sunt de aceeași culoare. Ie calul nu este fizic capabil de a ajunge la bate toate celulele, în cazul în care numai pentru că trebuie să se schimbe pe parcursul a 63 de celule de culoare, de exemplu, nu va mai fi cum ar fi în celula originală. Și aici am suferit. și cum să obțineți în jurul întregii bord. și care are pentru că algoritmii, etc. Iată câteva materiale pe acest subiect:
Pentru cei care nu prea amintesc se pare ca o tabla de sah:
Deci Am prins calul meu atât de mult încât am decis să adăugați codul sursă găsit pe a doua metodă de testare de referință pentru Varnsdorf. „Cand crawling placi de cal ar trebui să fie pe teren unde puteți merge pentru numărul minim nu a trecut încă câmpurile. Dacă există mai multe câmpuri, puteți merge la oricare dintre ele.“
Cu toate acestea, după cum se menționează în Wiki o inexactitate în această regulă. Dacă există mai multe câmpuri sunt conforme cu normele, atunci ele nu sunt toate egale și alegere teoretic greșită poate face un cal într-un impas. Imeeno de ce am decis să ia o metodă recursiv, dar nu merg peste tot posibile domenii de curs, și numai acelea care îndeplinesc această regulă, ceea ce reduce semnificativ numărul de întoarce și timpul de execuție a algoritmului.
Nu e chiar cea mai bună sursă de ceea ce sa întâmplat poate fi vizualizat aici. Apropo, IdeOne'e se poate vedea nu numai codul sursă, dar, de asemenea, pentru a le lansa pentru executare. Ei bine, cu ajutorul unor modificări ușor poate duce, în general, un cal oriunde;) De exemplu, calul trebuie să provină din A8 în H8, nimic nu ar putea fi mai simplu:
Vrei o altă opțiune? Prea, te rog:
Și este posibil, dacă se dorește, și să contorizați toate aceste variante. În general, problema cu cavalerul de by-pass de tablă de șah poate fi acum rezolvate cu ușurință. Apropo, în rețeaua de spațiu, datorită wiki, am găsit demonstrație GUI a acestei metode. Îl puteți descărca de aici. Aplicația este scris Ahmetovym Igorem și vă permite să vizualizați procesul de traversal. Puteți alege diferite setări și începe poziția calului:
P.S. Apropo, pentru cei care sunt agățate pe tema cal-Jaretul tematice joc Cavalerul Anton Lashkov, în cazul în care toată lumea va fi în măsură să sară pe cal la fel de mult ca 44 de niveluri pe dispozitivul Android;) Asta e tot pentru azi.