| Fişierul intrare/ieşire: | go.in, go.out | Sursă | Concursul National Urmasii lui Moisil 2011 - Clasa a 9-a |
| Autor | Alexandru Paicu | Adăugată de |  Andrici Cezar •andrici_cezar |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate |   2/5 |
Vezi solutiile trimise | Statistici
Go
Claudia joacă GO cu calculatorul. Strategia ei este simplă dar eficientă: la fiecare mutare va alege să pună o piesă astfel încât să captureze cât mai multe din piesele adversarului. În cazul în care există mai multe variante, va alege să plaseze piesa pe un rând cât mai sus iar dacă în continuare există mai multe variante, va plasa piesa cât mai în stânga. Jocul de GO se desfăşoară pe o tablă dreptunghiulară cu N x M căsuţe dispuse pe N linii şi M coloane.
Regulile sunt:
- Jucătorii mută alternativ, plasând câte o piesă pe o căsuţă neocupată a tablei.
- Toate piesele de aceeaşi culoare care sunt adiacente pe orizontală sau verticală formează un grup. Două piese sunt adiacente dacă cele două căsuţe în care ele sunt plasate au o latură comună.
- Dacă mutarea unui jucător va conduce la eliminarea libertăţilor unui grup de piese ale adversarului, acele piese sunt capturate şi eliminate de pe tablă. Libertăţile unui grup sunt toate căsuţele goale care sunt adiacente cu cel puţin o piesă din grup.
Dându-se o configuraţie a tablei de GO, ajutaţi-o pe Claudia să aleagă mutarea corectă astfel încât să captureze cât mai multe dintre piesele adversarului, în condiţiile enunţate mai sus.
Date de intrare
Pe prima linie a fişierul go.in se găsesc două numere naturale N şi M care reprezintă numărul de linii respectiv de coloane ale tablei de joc. Pe următoarele N linii se află configuraţia curentă a tablei de joc (0 reprezintă căsuţă neocupată, 1 - o piesă a Claudiei, 2 - o piesă a adversarului).
Date de ieşire
Fisierul go.out trebuie să conţină pe prima linie două numere separate printr-un singur spaţiu. Acestea reprezintă indicele liniei, respectiv indicele coloanei, unde trebuie plasată piesa conform strategiei Claudiei (se începe numerotarea liniilor şi coloanelor de la 0).
Restricţii
Fişierul de intrare conţine o configuraţie validă (fiecare grup de piese are cel puţin o libertate, altfel ar fi fost deja capturat). De asemenea, pe tabla de joc există cel puţin o poziţie pe care Claudia poate plasa o piesă.
- 1 ≤ N, M ≤ 1000
Exemplu
| go.in | go.out |
|---|---|
| 5 7 0 1 2 2 2 0 2 0 1 2 2 1 2 1 0 0 1 1 2 2 0 0 1 2 2 0 1 2 0 0 1 1 2 0 0 | 0 5 |
| 3 4 1 0 1 0 0 2 0 2 1 1 2 2 | 0 1 |
Explicatie
In primul exemplu, plasând piesa pe poziţia (0,5), Claudia va captura 6 piese (grupul din stânga acestei piese format din cinci valori egale cu 2 şi adiacente, plus grupul format din piesa de la poziţia (0,6)). Oriunde altundeva va face mutarea, Claudia nu va putea captura la fel de multe piese.
In cel de-al doilea exemplu, Claudia nu poate captura mai mult de 0 piese, oriunde ar plasa noua piesă. Astfel, ea va alege să pună piesa pe rândul cel mai de sus şi cât mai în stânga pe acel rând.
