Burtu spēle

ID: letters
Grūtība: 3/5
Laika limits: 1

Uzdevums

Viena spēlētāja burtu spēle tiek spēlēta uz taisnstūrveida R rindu un C kolonnu liela rūtiņu laukuma, kura katrā rūtiņā ir ierakstīts kāds angļu alfabēta lielais burts.

Spēles sākumā spēļu kauliņš atrodas laukuma kreisā augšējā stūrī (laukuma rūtiņā, kas atrodas pirmajā rindā un pirmajā kolonnā). Katrā gājienā spēlētājs drīkst kauliņu pārvietot uz rūtiņu, kurai ar iepriekšējo kauliņa atrašanās rūtiņu ir kopīga mala. Vienīgais ierobežojums ir, ka kauliņš nedrīkst nonākt tādā rūtiņā, kurā ierakstīts tāds pats burts kā kādā no iepriekš apmeklētajām rūtiņām.

Uzrakstiet programmu, kas nosaka, kādu lielāko gājienu skaitu spēlētājs var izdarīt!

 

Ievaddati

Teksta faila letters.in pirmajā rindā dotas divu naturālu skaitļu R un C vērtības (1 ≤R,C≤20).

Katrā no nākošajām R faila rindām dots pa C burtiem katrā. j-tais burts faila i+1-ā rindā ir tabulas i-tās rindas j-tajā kolonnā ierakstītais burts.

 

Izvaddati

Teksta faila letters.out vienīgajā rindā jāizvada lielākais iespējamais izdarīto gājienu skaits.

 

Piemērs

letters.inletters.out
2 4
CAAB
ADCB
3
  
letters.inletters.out
3 6
HFDFFB
AJHGDH
DGAGEH
6
  
letters.inletters.out
5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH
10

 

Atsauces

Uzdevums izmantots Horvātijas informātikas olimpiādē 2002.gadā
© 2001-2002 olimps! http://www.lio.lv/olimps/