.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » joc5

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
joc5


Timp maxim de executie/test:
0.1 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

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

joc5.in joc5.out joc5.in joc5.out joc5.in joc5.out

3 4
.C#.
B...
##C.
3
1 1
1 4
2 3

 

ANA
ION
ANA

4 5
.#...
#.#.S
.#..S
.#...
3
3 1
3 3
1 5

 


ANA
ANA
ANA
5 6
##..#.
..#SC#
..#..#
###...
.....B
4
2 1
5 1
1 4
1 6


ANA
ANA
ION
ION

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi

Contact:ema at mail.dntis.ro

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2004: cifre1, super, apm, bile1, factk, schimb, caini, secvreg, descfib, maraton, masina1, otilia, multiplu, tub, pasune, remi, m01, robot1, na, sir23, paralel, zaruri, bomboane, dotnet, divizor, tren1, tvshow, pachete, soldati1, echipe, omizi, suma1, aedaro, concurs1, windows, comb, renju, latime, vectori, ghici, subperm, puncte, mere1, spirala, distanta, piloti
De acelaşi autor: celule, scp, vedete, film, ab, supertri, inginer, camp, sl, detinut, simetric, egal, gropi, ruleta, carti, tgv, uscat, afise, dezbateri, bunici, rv, onu, nspecial, secvop, cadou, chimie, reteta, piticot, petrol, checkin, teanc, index, teren, pizza, ecran, drum, text, lbd, aven, spam, pluricex, tren2, gray, pasi, mgo, joc, anagrame, vecini, criptmat, maxim, cutie, party, friends, net, sablon, hd, pc, sir2, aztec, scara, nr, robot2, sah, formule, ed, bilete, hanoig, flood, matrice3, erdos, grup, cd, kfactor, np, cuc, radio, honest, ref, nr01, scor2, convert, auto2, compress, politics, pm, playlist, barbie, firma1, submatrix, ham, pizza1, exam, ants, teatru1, cifre1, bile1, caini, secvreg, pasune, remi, m01, sir23, tren1, pachete, aedaro, windows, renju, latime, mere1, piloti, peste, pitici, sirag1, stive, turn1, carti1, program1, spioni, kgb, lift, apel, lex, oras, homeless, subsir, dist, harta1, adevar, joc10, bare, zapezi, masina2, perechi1, raft, joc11, joc12, ferma, fni, tunel, lover, pepsi, transport, avion, monkey, premii1, garaj, carti2, tv, pact, fat, cafea, echipe1, secvente, petrom, peg, scara1, lant, ecuatii, stiva, bile4, jungla, rj, poli, text1, compus1, rez, politie, anag, codul, coment, muzeu, seti, basm, timer, secvsir, dp, placa, prod3, bursa, submdisj, sotron1, fazan, secvpar, joker, lego, medalii, cfr, antipatie, figura, links, segm, colorare, brazi, mobil, distsir, guess, greiere, pestera, conferinta, chei, ny, nx, ghinion, sumb, drenaj, telecomanda, grupuri, mahjong, rotund, viena, sport2, cos, monoton, micro, valet, nr0, maxviz, anagramabil, nrpal, lista, dame, consiliu, adprod, arme, deal, prodnr, compar, latin, interviu, vintage, prize, nrdiv, arrows, tdrept, agenda, reziston, vot2, tema, smiley, relatii, ech, scadere, nebuni, castig, expand, wb, prime2, virgule, b210
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
Software recomandat
surse trimise | ajutor