Državno natjecanje 2017. / Osnovna škola (8. razred) - 2. zadatak

Marin je od Ivana za rođendan dobio dvodimenzionalnu slagalicu koja se sastoji od N stupaca i N redaka. Svako polje slagalice je crne ili bijele boje.

Tijekom rješavanja slagalice Marin može rotirati (ciklički pomicati) sva polja nekog retka ili stupca za proizvoljan broj polja ulijevo ili udesno, odnosno prema gore ili prema dolje.

Na slici možeš vidjeti primjer dvaju Marinovih poteza.

U prvom potezu Marin rotira drugi redak matrice za dva polja udesno, a u drugom potezu treći stupac za jedno polje prema gore:

Polja slagalice numerirana su po redcima počevši redom od prvog polja prvog retka. Npr. ako je slagalica dimenzija 5x5, tada je numeracija kao na slici. Brojevi upisani u polja slagalice ne mijenjaju se Marinovim potezima.

Ako slagalica ima C crnih polja, za nju kažemo da je riješena ako se crna polja nalaze u prvih C polja slagalice, tj. u poljima s brojevima od 1 do C. Pomozi Marinu riješiti slagalicu!!!

ULAZNI PODATCI

U prvom retku nalazi se prirodan broj N (2 ≤ N ≤ 10).

U svakom od sljedećih N redaka nalazi se N znakova koji predstavljaju polja slagalice. Znak može biti ‘x’ (simbol za crno polje) ili ‘o’ (simbol za bijelo polje).

IZLAZNI PODATCI

Potrebno je ispisati neki niz poteza kojim Marin može riješiti slagalicu.

Za svaki potez ispiši jedan redak u kojem se nalaze tri elementa.

Prvi element može biti 'R' što označava rotaciju retka slagalice, ili 'S' što označava rotaciju stupca slagalice.

Drugi element je redni broj retka/stupca koji Marin rotira te je taj broj iz skupa {1..N}.

Treći element predstavlja broj polja za koji Marin rotira redak/stupac u tom potezu te je taj broj između -(N - 1) i N - 1, uključivo.

Negativan broj predstavlja rotaciju ulijevo, odnosno prema gore, a pozitivan udesno, odnosno prema dolje.

Nakon svih ispisanih poteza u novi redak ispiši znak 'K' kao znak da Marin neće raditi više poteza.

Rješenje ne smije sadržavati više od 104 poteza.

PRIMJERI TEST PODATAKA

Ulaz

3
xox
oxo
oox

Izlaz

S 3 1
S 2 -1
R 2 -2
K

Ulaz

3
oxx
xxo
xxx

Izlaz

S 1 1
R 2 2
S 3 1
S 2 -2
K