Nejkratší cesta šachovým králem – Pascal – Fórum – Programujte.com

TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

Trvalé přihlášení

Zapomněl jsi heslo?

Nejkratší cesta šachovým králem – Pascal – Fórum – Programujte.com

Rozšířené hledání ›

Nejnovější témata ve fóru

22:06, Startupy Megastroj.cz – Vše na jednom místě: půjčovna, bazar a inze…

21:17, Inzerce FPGA vývojová deska XILINX VIRTEX 5 ML507

20:59, OS - GNU / Linux Ubuntu a OpenSuse

21:47, Offtopic Digitalizace v Česku

10:10, Cinema 4D Export USDC do DaVinci Resolve

16:58, Photoshop Jak odstranit (potlačit) odlesky

Stavba Laser Arény
Laser Game Brno

Fórum › Pascal

Nejkratší cesta šachovým králem

nordec

~ Anonymní uživatel
~ 2 příspěvky

3. 11. 2008 #1

Potřebuji poradit jak napsat program, který bude hledat nejkratší cestu šachovým králem na šachovnici 8x8, kde na některá políčka nelze vstoupit.

Vstup programu obsahuje popořadě:

počet překážek
souřadnice jednotlivých překážek (dvojice čísel v rozsahu 1..8)
souřadnice výchozího políčka
souřadnice cílového políčka políčka
Čísla ze vstupu čtěte procedurou read.

Výstup je buď -1, pokud král na cílové políčko nemůže dojít NEBO počet kroků, které musí vykonat.

Příklad vstupu:
1
2 1
1 1
2 2
Odpovídající výstup:
1

Předem dík za rady.

Nahlásit jako SPAM

IP: 85.160.109.–

Blog.Glor.cz - blog nejenom o cestování

Osiris0

Stálý člen

3. 11. 2008 #2

To nordec : Prohledávání do šířky například?

Nahlásit jako SPAM

IP: 85.70.130.–

nordec

~ Anonymní uživatel
~ 2 příspěvky

3. 11. 2008 #3

Může být, hlavně aby to ze vstupních dat spočetlo počet kroků krále. Tušim, že podle algoritmu vlny. Jak to ale udělat, to nemám zdání.

Nahlásit jako SPAM

IP: 85.160.109.–

Santas 0

Věrný člen

3. 11. 2008 #4

a ty cakas, ze ty to tu len tak niekto naprogramuje :smile5:

Nahlásit jako SPAM

IP: 195.91.79.–

http://psandtner.sk/blog

drobas

~ Anonymní uživatel
~ 17 příspěvků

3. 11. 2008 #5

to nordec...nepripomina mi to nahodou priklad do codexu? (zdravim kolegu :-D)

a) udelej si normalne pole 8x8 of integer, na zacatku vsechny policka inicializuj na 0
b) precti souradnice prekazek a na jejich misto dej treba 100 to je jedno
c) precti hodnotu pocatecni souradnice krale a oznac okolni mista, ktera maji nulu hodnotou 1 --> postupuj dale a oznac vsechny okolni 2 (pokud maji nulu) --> atd atd (proste vlna)
d) potom uz jen staci precist hodnotu ktery ti vysla na cilovem policku

je to peknej priklad, klidne bych se do toho pustil, ale nak se mi chce spat...

good luck

drobas

Nahlásit jako SPAM

IP: 195.113.69.–

drobas

~ Anonymní uživatel
~ 17 příspěvků

3. 11. 2008 #6

resp policka inicializuj na -1 abys to mel lepsi, vlnu opakuj pro max 34 opakovani (nejhorsi pripad)...

Nahlásit jako SPAM

IP: 195.113.69.–

~ Anonymní uživatel
~ 1 příspěvek

4. 11. 2008 #7

To drobas : Proč 34?

Nahlásit jako SPAM

IP: 83.208.235.–

KIIV

~ Moderátor

+43

God of flame

4. 11. 2008 #8

ta "vlna" je vesmes ohodnocovani hran grafu.. jen tady je kazda spojnice stejne dlouha...

Nahlásit jako SPAM

IP: 80.250.27.–

_{Program vždy dělá to co naprogramujete, ne to co chcete...}

drobas 0

Newbie

4. 11. 2008 #9

to nf... 34 je maximalni cesta kterou muzes tomu krali zaridit...to je kdyz to bude takhle (snad se to nenaformatuje blbe :-))
0-------
00000000
-------0
00000000
0-------
00000000
-------0
00000000

(pomlcky sou prekazky) a startovni pozice (1,1) a cilova (8,1)

Nahlásit jako SPAM

IP: 195.113.69.–

Mircosoft+1

Věrný člen

4. 11. 2008 #10

Možná by se dalo využít něco z tohohle: http://int21h.ic.cz/?id=93 (stačí to zjednodušit nastavením vah všech přechodů ve všech směrech na 1).

Nahlásit jako SPAM

IP: 147.32.161.–

Chceš-li lepší odpověď, polož lepší otázku.
Moje stránka.

MZetko 0

Stálý člen

4. 11. 2008 #11

drobas napsal:
resp policka inicializuj na -1 abys to mel lepsi, vlnu opakuj pro max 34 opakovani (nejhorsi pripad)...

To si nemyslím. Podle mě je nejdelší cesta 40 -

VVVVVVVV

XXXXXXXV

VVVVVVXV

VXXXXVXV

VXVXXVXV

VXVVVVXV

VXXXXXXV

VVVVVVVV

Nahlásit jako SPAM

IP: 83.208.235.–

"Přirozená inteligence bude umělou brzy překonána. Přirozenou blbost však umělá nemůže nahradit nikdy"
Jára da CIMRMAN
http://www.newgame.cz

drobas 0

Newbie

5. 11. 2008 #12

pravda...takhle me to nanapadlo :-D...tak 40 je konecna varianta, vic uz to nepude :-)

Nahlásit jako SPAM

IP: 195.113.69.–

Taniak

~ Anonymní uživatel
~ 1 příspěvek

19. 12. 2017 #13

#11 MZetko
#11 MZetko
Asi zabúdate, že král môže po šachovnici chodiť aj diagonálne, takže táto "najdlhšia" cesta má v skutočnosti tiež dĺžku 34.

Nahlásit jako SPAM

IP: 78.128.189.–

Kit+15