Tabla de joc a unui foarte
popular joc de pe Internet consta dintr-o zona dreptunghiulara de pe ecran,
zona impartita in celule, organizate in M
linii si N coloane.
Liniile sunt numerotate de la 1
la M, incepand de la
linia de sus,
iar coloanele sunt numerotate de la 1
la N incepand de
la coloana din stanga.
Fiecare celula contine o piesa de o anumita culoare. Culorile sunt codificate
prin litere mare ale alfabetului englez.
Scopul jocului este de a
obtine grupuri de cel putin 3
piese de aceeasi culoare. Un grup este format din cel putin trei piese de aceeasi
culoare aflate in celule alaturate situate pe o aceeasi linie sau situate pe
o aceeasi coloana. In figura urmatoare piesele de culoare R
formeaza un grup de 4 piese, piesele de culoare V
formeaza un grup de 3 piese, insa piesele de culoare ANU formeaza un grup:
T
B
C
C
E
F
G
H
V
N
R
R
R
R
U
P
V
X
A
B
C
D
E
L
V
A
A
M
N
U
P
T
In scopul crearii grupurilor
de piese sunt permise doua tipuri de mutari si anume:
1. Se selecteaza o linie a tablei si se permuta circular spre dreapta cu un
anumit numar de pozitii, bilele care "ies" prin partea din dreapta
a tablei fiind mutate la inceputul liniei. De exemplu pentru urmatoarea configuratie
a tablei: ABAD
BADC
ABCD permutarea liniei
a doua cu o pozitie la dreapta conduce la configuratia: ABAD
CBAD
ABCD
si astfel s-au format
doua grupuri de cate trei piese (una pe coloana a doua si una pe coloana a patra)
2. Asemanator se poate selecteaza o coloana a tablei care se permuta circular
in jos cu un anumit numar de pozitii, piesele ce "ies" prin partea
de jos a tablei fiind mutate la inceputul coloanei respective.
O mutare este permisa doar daca in urma ei se formeaza cel putin un grup de
piese care vor fi eliminate.
Doua mutari sunt diferite daca nu implica aceeasi linie sau aceeasi coloana,
sau in cazul in care implica aceeasi linie sau aceeasi coloana, difera numarul
de pozitii permutate circular la cele doua mutari.
Cerinta
a) Sa se determine numarul
de posibilitati de a realiza prima mutare pentru o tabla de joc data.
b) Sa se determine numarul maxim de piese ce se pot elimina in urma primei mutari,
numar ce este egal cu suma numarului de piese din toate grupurile ce se formeaza
in urma mutarii respective.
c) Sa se determine prima mutare ce trebuie sa fie executata, astfel incat numarul
de piese ce se pot elimina sa fie maxim posibil. Daca exista mai multe solutii,
este preferata cea care executa permutarea unei linii. Daca si in acest caz
exista mai multe solutii se alege varianta cu indicele de linie minim, iar pentru
aceeasi linie, cea cu numarul de pozitii pe care se executa permutarea minim.
Date de intrare
Pe prima linie a fisierului
de intrare game.in sunt
scrise doua numere naturale M
si N, separate
printr-un singur spatiu, reprezentand numarul de linii si de coloane ale tablei
de joc. Fiecare dintre urmatoarele
M linii contine
cate N litere
mari ale alfabetului englez, reprezentand culorile pieselor de pe tabla de joc.
Date de iesire
Prima linie a fisierului
game.out va contine un
singur numar natural reprezentand numarul de posibilitati de a realiza prima
mutare. Linia a doua a fisierului va contine un singur numar natural reprezentand
numarul maxim de piese ce se pot elimina in urma efectuarii primei mutari. Pe
linia a treia se scrie o mutare care duce la eliminarea unui numar maxim de
piese de pe tabla de joc. O mutare este codificata prin trei numere naturale
x, y,
z separate prin
cate un spatiu avand urmatoarele semnificatii:
- x
are valoarea 1
daca se permuta o linie, respectiv 2
daca se permuta o coloana;
- y
reprezinta numarul de ordine al liniei sau al coloanei care se permuta;
- z
reprezinta numarul de pozitii cu care se face permutarea circulara.
Restrictii
3
<= M, N <= 50
Pentru toate datele de
test va exista cel putin o mutare posibila.
Initial tabla nu contine
grupuri.
1<=z<=N-1.
Exemplu
game.in
game.out
game.in
game.out
3
4
DBAD
AADA
DBCA
4
6
1 2 2
3
4
ABAD
BADC
ABCA
3
3
1 2 1
prof. Popescu
Carmen Colegiul National
"Gheorghe Lazar" Sibiu
Contact: carmen_cngl@yahoo.com