go

Go

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

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

1 1 2 2 | 0 1 |

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

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