Nosaukums
Burtu spēle (letters)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
75%

Definīcija

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!


Ievaddatu raksturojums

Ievaddatu 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.


Izvaddatu raksturojums

Izvaddatu vienīgajā rindā jāizvada lielākais iespējamais izdarīto gājienu skaits.


Piezīmes

Uzdevums izmantots Horvātijas informātikas olimpiādē 2002.gadā


Paraugdati

Stdin
2 4
CAAB
ADCB
Stdout
3

Stdin
3 6
HFDFFB
AJHGDH
DGAGEH
Stdout
6

Stdin
5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH
Stdout
10

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.