Nejkratší cesta šachovým králem – Pascal – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

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

 

nordec
~ Anonymní uživatel
2 příspěvky
3. 11. 2008   #1
-
0
-

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.–
Osiris0
Stálý člen
3. 11. 2008   #2
-
0
-

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
-
0
-

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.–
Santas0
Věrný člen
3. 11. 2008   #4
-
0
-

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
-
0
-

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
-
0
-

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.–
nf
~ Anonymní uživatel
1 příspěvek
4. 11. 2008   #7
-
0
-

To drobas : Proč 34?

Nahlásit jako SPAM
IP: 83.208.235.–
KIIV
~ Moderátor
+43
God of flame
4. 11. 2008   #8
-
0
-

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...
drobas0
Newbie
4. 11. 2008   #9
-
0
-

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
-
0
-

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.
MZetko0
Stálý člen
4. 11. 2008   #11
-
0
-

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
drobas0
Newbie
5. 11. 2008   #12
-
0
-

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
-
0
-

#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
Guru
21. 12. 2017   #14
-
0
-

#12 drobas
V každém případě se algoritmus dá ukončit ve chvíli, kdy král dosáhne cíle.

Nahlásit jako SPAM
IP: 194.228.68.–
Komentáře označují místa, kde programátor udělal chybu nebo něco nedodělal.
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 2 hosté

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032024 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý