Lielākais rīma

Uzdevums

Armands un Dāvis spēlē spēli "Lielākais rīma". Spēle norisinās uz taisnstūrveida R rindu un C kolonnu rūtiņu laukuma. Spēles noteikumi ir sekojoši:

• Uz laukuma atrodas viens spēles kauliņš, kuru pēc kārtas pārvieto katrs no spēlētājiem.
• Vienā gājienā kauliņu var pārvietot uz blakus rūtiņu sekojošos virzienos: uz leju, pa labi vai pa diagonāli uz leju pa labi.
• Dažas rūtiņas ir "aizliegtas" - uz tām kauliņu pārvietot nedrīkst.
• Katrā rūtiņā var atrasties viena no sekojošām ēdamlietām: hamburgers, kartupeļu salmiņi vai saldējums. Spēlētājs, kas pārvieto kauliņu uz rūtiņu ar ēdamlietu, saņem 1 punktu, ja šajā rūtiņā bija hamburgers, 3 - ja kartupeļu salmiņi un 5 - ja saldējums.
• Spēle beidzas, ja kāds no spēlētājiem nevar izdarīt gājienu (jo jebkurā no trim iespējamajiem virzieniem kauliņš nokristu no spēles laukuma vai arī nāktos ieiet aizliegtā rūtiņā).
• Ja spēles beigās abiem spēlētājiem ir vienāds punktu skaits, zaudējis ir tas spēlētājs, kuram jāizdara gājiens.
• Ja spēles beigās spēlētājiem ir dažāds punktu skaits, uzvarējis ir spēlētājs, kuram ir vairāk punktu.
• Spēles sākumā abiem spēlētājiem ir 0 punktu. Pirmais gājienu izdara Armands. Kauliņa sākotnējā atrašanās rūtiņa nav aiznliegta un tajā nav ēdamlietu.

Tā kā jebkura spēle ar šiem noteikumiem ir galīga, iespējams pierādīt, ka katrai kauliņa sākuma pozīcijai vienam no spēlētājiem ir uzvaroša stratēģija - t.i., šis spēlētājs var uzvarēt neatkarīgi no tā, kā spēlēs pretinieks.

Uzrakstiet programmu, kas dotai laukuma konfigurācijai un kauliņa sākotnējai atrašanās rūtiņai noskaidro, kuram no spēlētājiem ir uzvaroša stratēģija!

Ievaddati

Teksta faila lielrima.dat pirmajā rindā dotas divu naturālu skaitļu R(rindu skaits,2 ≤R≤100) un C(kolonnu skaits, 2≤C≤100) vērtības, kas atdalītas ar tukšumsimbolu.

Katrā no nākošajām R faila rindām dots pa C simboliem katrā, un tā apraksta kārtējo laukuma rindu. Ar '#' ir apzīmētas aizliegtās rūtiņas, ar 'C' ir apzīmētas rūtiņas ar hamburgeru, ar 'S' - ar kartupeļu salmiņiem, ar 'B' - ar saldējumu. Pārējās rūtiņas ir apzīmētas ar '.' (punktu).

Nākošajā faila rindā dota naturāla skaitļa N(dažādo kauliņa sākumpozīciju skaits, 1 ≤N≤100) vērtība. Katra no nākošajām N faila rindām satur divu naturālu skaitļu A(1≤A≤R) un B(1≤B≤C) vērtības, kas atdalītas ar tukšumsimbolu. A ir kauliņa sākumpozīcijas rindas un B - kolonnas numurs.

Rindas ir numurētas no augšas uz leju ar naturāliem skaitļiem no 1 līdz R pēc kārtas, savukārt kolonnas ir numurētas no kreisās puses uz labo pēc kārtas ar naturāliem skaitļiem no 1 līdz C.

Izvaddati

Teksta failam lielrima.rez jāsatur tieši N rindas. Faila i-tajā rindā jābūt burtam 'A', ja i- tajai dotajai kauliņa sākumpozīcijai uzvaroša startēģija ir Armandam, vai 'D', ja Dāvim.

Piemērs

lielrima.dat	lielrima.rez
3 4 .C#. B... ##C. 3 1 1 1 4 2 3	A D A
lielrima.dat	lielrima.rez
4 5 .#... #.#.S .#..S .#... 3 3 1 3 3 1 5	A A A
lielrima.dat	lielrima.rez
5 6 ##..#. ..#SC# ..#..# ###... .....B 4 2 1 5 1 1 4 1 6	A A D D

Atsauces