go

Go

== include(page="template/taskheader" task_id="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.

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

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

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$

* $1 ≤ N, M ≤ 1000$

h2. Exemplu

table(example). |_. go.in |_. go.out |_. Explicaţie |

table(example). |_. 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 | 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. |
| Ionescu | 12 | Constanta |

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 |

h3. Explicaţie

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

== include(page="template/taskfooter" task_id="go") ==
 

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.
 
== include(page="template/taskfooter" task_id="go") ==

7321