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

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


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

Ana si Ion au o pasiune comuna pentru sah si joaca ori de câte ori au timp liber. Fiind persoane non-conformiste, si-au comandat table de sah de diferite dimensiuni, si seturi de piese speciale. Daca nu au timp sa termine o partida, pastreaza pe tabla de sah piesele asa cum sunt si continua a doua zi.
De data aceasta, a aparut o problema - Ionel, fiul lor, a rasturnat din greseala tabla de sah - si ei încearca sa reconstituie acum ultima configuratie.
Ion îsi aminteste cu precizie cu arata ieri la începutul jocului configuratia tablei de sah, precum si mutarile pe care el le-a facut. Ana îsi aminteste ca a jucat ciudat - tot jocul a mutat aceeasi piesa, o tura. Nu îsi aminteste exact pozitiile în care a mutat, dar îsi aminteste directiile în care s-a deplasat tura.

Cerinta

Scrieti un program care sa determine pozitiile în care s-ar putea afla la final tura mutata de Ana.

Date de intrare

Fisierul de intrare sah.in contine pe prima linie doua numere naturale separate printr-un spatiu X N, reprezentând dimensiunea tablei de sah, respectiv numarul de piese de pe tabla de sah.
Urmatoarele N linii contin informatii despre pozitia pieselor de pe tabla. Mai exact, pe linia i+1 se afla pozitia piesei i sub forma a doua numere naturale printr-un spatiu L C, reprezentând linia si respectiv coloana pe care se afla piesa.
Ultima pozitie corespunde turei pe care o muta Ana.
Pe linia urmatoare se afla un numar natural Nr, reprezentând numarul de mutari efectuate de Ion si respectiv de Ana.
Pe fiecare dintre urmatoarele Nr linii se afla informatii despre mutarile facute de Ion.
Mai exact, pe linia N+2+j sunt scrise 3 numere naturale separate prin câte un spatiu i L1 C1 cu semnificatia piesa i este deplasata pe linia L1, coloana C1.
Pe ultima linie din fisier este scrisa o secventa de Nr caractere din multimea {'N', 'S', 'E', 'V'} care reprezinta în directiile în care a mutat Ana tura (caracterul i din aceasta secventa corespunde celei de a i-a mutari).

Date de iesire

Fisierul de iesire sah.out va contine pe prima linie un numar natural p, reprezentând numarul de pozitii finale posibile.
Pe urmatoarele p linii sunt scrise pozitiile finale posibile, câte o pozitie pe o linie. O pozitie este descrisa prin doua numere naturale separate printr-un spatiu L C, cu semnificatia "pe linia L si coloana C este o pozitie finala posibila". Pozitiile finale vor fi scrise în ordinea liniilor; daca exista mai multe pozitii finale pe aceeasi linie, acestea vor fi scrise în ordinea coloanelor.

Restrictii si precizari

1 < X<=50
1 < N <= 1000
0 < Nr <= 1000
Piesele sunt numerotate de la 1 la N.
Liniile tablei de sah sunt numeroate de sus în jos de la 1 la X, iar coloanele sunt numerotate de la stânga la dreapta de la 1 la X.
Ana si Ion muta alternativ, Ion a fost primul la mutare.
O tura poate fi mutata numai pe 4 directii:
nord (codificat N) - pe o linie cu indice mai mic, aceeasi coloana;
sud (codificat S) - pe o linie cu indice mai mare si aceeasi coloana
est (codificat E) - pe o coloana cu indice mai mare si aceeasi linie
vest (codificat V) - pe o coloana cu indice mai mic si aceeasi linie
La o mutare o piesa trebuie sa se deplaseze din pozitia curenta.

Exemplu
sah.in sah.out

5 8
2 2
3 2
4 3
5 4
4 5
3 5
2 5
2 4
4
3 4 2
4 5 3
1 1 2
2 5 1
SVNV

4
2 1
2 2
3 1
3 2

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi
Contact:emanuela.cerchez@gmail.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2006: scara, programs, nr, iepuras2, numere3, robot2, fry, suma, formule, perm, cifra, repeat, ture, xor, policefm, unu, criptare, ed, bilete, vector, scor, ratb, infinit, race, dragon, kreg, placi, hanoig, red, 2sec, flood, sume3, balls, festival, croco, johnie, matrice3, pavaj, sume, arthur, kimberley, kafka, vocale, pento, prop, ro, sol, bacan, erdos, poligon, reduceri, druid, novel, gramezi, nrbinar, laser, spair, caravane, cuburi, grup, invest, cd, friends2, mese, toys
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, 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, joc5, 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 coada: balanta, inginer, camp, rebus, harta, insule, volei, lbd, magic3, axa, cadere, reinvent, ocean14, iepuras2, balls, cd, toys, radio, caini, subperm, castel, excursia, casute, soricel2, masina2, salvare, paianjen, suma2, garaj, alee, lanterna, rj, caraibe, taxe1, sotron1, lanturi, tom, k1, dreptunghiuri, sokoban, ny, oldest, drumuri1, alpinist, tsunami, robot3, joc19, valet, oras1, gheizere, zone, taxa, abq, cartite, joc21, traseu3, panda, expand
Despre Lee: inginer, insule, lbd, ocean14, iepuras2, radio, lacuri, castel, excursia, soricel2, masina2, paianjen, suma2, soricel3, cub2, alee, rj, taxe1, sotron1, tom, ny, ai, robot3, pixy, valet, oras1, maxtri, lgdrum, gheizere, abq, cartite, joc21, traseu3, wow, panda
Software recomandat
surse trimise | ajutor