Matematické Fórum

Ahoj,
rozděl si problém, to často pomáhá. Vlastně jde o opakované hledání nejkratší cesty právě dvojice znaků, cesta při hledání neovlivní cestu při hledání jiné dvojice. To znamená, že když budeš hledat např. slovo "VUZ" a začínáš vlevo nahoře, tedy na znaku "A", hledáš vlastně postupně nejmenší cestu "AV", "VU" a "UZ". Takže ti jde jen o to, abys našel nejmenší cestu dvou znaků.

Jistě si můžeš klávesnici nějak reprezentovat grafem a pak na to napálit Dijskrův algoritmus, ale to je trochu kanón na vrabce. Místo toho se můžeš zamyslet nad strukturou matice:
1. Znaky "Y" a "Z" jako výchozí si ošetři zvlášť třeba tak, že pokud půjde o cestu "YZ" (např. ve slově "kyz") nebo "ZY" (např. ve slově "zygota"), vyřeší to první podmínka. V opačném případě dáš jeden krok "nahoru" a "Y" přejde v "Q" a "Z" přejde v "R".

2. Ostatní znaky máš v tabukce 3x8, srovnané podle abecedy. Tady už můžeš celkem snadno operovat s tím, že znaky jsou v obvyklých jazycích ordinální typ. Když si klávesnici přepíšeš po pořadových číslech, dostaneš:

01 02 03 04 05 06 07 08
09 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24

Většina jazyků má operace celočíselného dělení a zbytku po celočíselném dělení, tím už snadno určíš souřadnice znaku. A protože jsou to čtverečky, můžeš si souřadnice dvou znaků spojit po "L", tj. nejdřív pohybem nahoru/dolů vyrovnáš řádek, potom doprava/doleva vyrovnáš sloupec.

↑ Stýv:
Díky, máš pravdu, tohle jsem tak nějak přehlédl :-(

↑ cetis:
Pokud se mohou písmena, je to trochu složitěší v tom, že tabulka není tak hezky učesaná. Jedno z možných řešení je tabulku reprezentovat nějakou hezkou dynamickou strukturou, která bude udržovat o každém písmeni informaci o jeho souřadnicích v tabulce. Tím, že se může opakovat, můžeš dostat i několik výsledků, z nich musíš uvažovat vlastně všechny, protože výběr aktuálně nejlepší dráhy může vést k horšímu výsledku o znak později.

První nápad za situace odpovídající zadání je ten, že si postupně sestrojíš všechny možné průchody klávesnicí a vybereš ten nejlepší. Např. budeš mít tabulku písmen se souřadnicemi:
A->[1,1]->[3,3]
B->[1,2]->[2,1]
C->[2,2]
(A a B je 2x)

Dostaneš sekvenci "ACAB", kterou si přepíšeš na sekvence uspořádaných dvojic
[1,1]->[2,2]->[1,1]->[1,2]
[1,1]->[2,2]->[3,3]->[1,2]
[3,3]->[2,2]->[1,1]->[1,2]
[3,3]->[2,2]->[3,3]->[1,2]
[1,1]->[2,2]->[1,1]->[2,1]
[1,1]->[2,2]->[3,3]->[2,1]
[3,3]->[2,2]->[1,1]->[2,1]
[3,3]->[2,2]->[3,3]->[2,1]

A z nich vybereš prostě tu nejkratší lomenou čáru měřeno v "taxikářské" míře.
Rozmysli si, jestli jde poslední řádek ošetřit tak, že natvrdo skočíš o řádek nahoru.

Přímočará programová realizace je taková, že si budeš do fronty sypat jednotlivé body, při každém větvení (více kláves se stejným písmenem) prostě frontu zduplikuješ a na konci dostaneš fronty odpovídající všem možným kombinacím. To je ale docela plýtvání pamětí. První nápad na optimalizaci je ten, že budeš hledat nejkratší cestu po částech, vždy jen do nejbližšího písmena, které je na klávesnici pouze jednou. (je třeba ošetřit poslední znak). Nebo se můžeš zamyslet víc než já a popřemýšlet o možnostech rekurze...