joc
Ana
si Ion joaca un joc interesant. Jocul are o tabla asemanatoare unei table de
sah, dar de forma dreptunghiulara, formata din R
linii (numerotate de sus în jos de la 1
la R) si C
coloane (numerotate de la stanga la dreapta de la 1
la C). Regulile jocului sunt:
1. Pe tabla se afla o singura piesa care este mutata alternativ de cei doi jucatori.
2. Mutarea piesei consta in deplasarea acesteia in unul dintre patratele adiacente
pozitiei sale curente, in una dintre directiile: jos, dreapta sau in diagonala
dreapta-jos. Mai exact daca piesa se afla pe linia i
si coloana j, ea poate fi mutata
in una dintre pozitiile (i+1,
j) - jos; (i,
j+1) - dreapta; (i+1,
j+1) - diagonala dreapta-jos.
3. Unele dintre patratele de pe tabla sunt "interzise" (adica piesa
nu poate fi mutata pe aceste patrate)
4. Un patrat de pe tabla poate sa contina cel mult unul dintre urmatoarele dulciuri:
o ciocolata, un suc, o bomboana. Jucatorul care muta piesa intr-un patrat care
contine o ciocolata primeste 1 punct, cel care muta piesa într-un patrat
cu suc primeste 3 puncte, iar cel care muta piesa intr-un patrat cu bomboana
primeste 5 puncte.
5. Jocul se termina cand jucatorul care se afla la mutare nu mai poate muta
(pentru ca piesa ar cadea de pe tabla sau ar intra intr-un patrat interzis in
oricare dintre cele 3 directii).
6. Daca la sfarsitul jocului ambii jucatori au acelasi numar de puncte, atunci
cel care nu a mai putut muta piesa pierde jocul.
7. Daca la sfarsitul jocului cei doi jucatori au punctaje diferite, cel cu punctaj
mai mare castiga jocul.
8. Ambii jucatori au 0 puncte la inceputul jocului. Ana face prima mutare. Piesa
se afla initial intr-un patrat care nu este interzis si care nu contine mancare.
Numarul de mutari ce poate fi facut este finit. Pentru orice configuratie a tablei si orice pozitie initiala a piesei, unul dintre jucatori (Ana sau Ion) poate castiga (spunem ca are strategie de castig), indiferent cum joaca celalalt jucator.
Cerinta
Se cunoaste
configuratia tablei de joc si o secventa de pozitii initiale ale piesei.
Scrieti un program care sa determine pentru fiecare pozitie initiala a piesei
cine are strategie de castig.
Date de intrare
Fisierul
de intrare joc.in contine pe
prima linie doua numere naturale separate printr-un spatiu R
C, reprezentand numarul de linii si respectiv numarul de coloane de pe
tabla de joc. Fiecare dintre urmatoarele R
linii contine o succesiune de C
caractere; linia i+1 din fisier
reprezinta linia i de pe tabla
de joc. Patratele interzise sunt reprezentate dintr-un caracter '#'.
Patratele care contin dulciuri sunt reprezentate cu literele 'C'
(pentru ciocolata), 'S' (pentru
suc) sau 'B' (pentru bomboana).
Celelalte patrate sunt reprezentate prin caracterul punct '.'.
Urmatoarea linie contine un numar natural N,
care reprezinta numarul de pozitii initiale pentru piesa. Fiecare dintre urmatoarele
N linii contine doua numere naturale
separate printr-un spatiu A B
(1<=A<=R, 1<=B<=C),
reprezentand linia si respectiv coloana pe care se afla initial piesa.
Date de iesire
Fisierul de iesire joc.out contine N linii. Linia i din fisierul de iesire va contine numele jucatorului (ANA sau ION, scris cu majuscule) care are strategie de castig pentru cea de a i-a pozitie initiala a piesei.
Restrictii
2<=R, C
<= 100
1<=N<=100
Exemple
| joc.in | joc.out | joc.in | joc.out | joc.in | joc.out |
|
3 4
|
ANA ION ANA |
4 5
|
ANA ANA ANA |
5
6 ##..#. ..#SC# ..#..# ###... .....B 4 2 1 5 1 1 4 1 6 |
ANA ANA ION ION |
Timp maxim de executie/test:
0.1 secunde
prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil"
Iasi
Contact:ema
at mail.dntis.ro