Go
A Go játékban két játékos felváltva helyez el fekete és fehér "köveket" egy $n \times n$ rács rácspontjaira. Céljuk minél nagyobb terület közrezárása, ahol már nincsenek kövek a rácspontokon.
A játék végén egy játékos pontszáma a körbekerített területein lévő üres rácspontok számának összege. A fekete és fehér kövek helyének ismeretében meg kell határoznunk a játékosok pontszámát, hogy megtudjuk, ki nyert.
A játék végén egy játékos pontszáma a körbekerített területein lévő üres rácspontok számának összege. A fekete és fehér kövek helyének ismeretében meg kell határoznunk a játékosok pontszámát, hogy megtudjuk, ki nyert.
Az itt leírtak nem egyeznek pontosan a Go szabályaival, feltettük, hogy: (a) minden terület "semleges", aminek mindkét színű határköve van; (b) minden kőcsoport "élő".
Formálisan: két rácspont $(r, c)$ és $(r', c')$ szomszédos, ha $ |r − r' | + |c − c' | = 1$. Üres rácspontok egy összefüggő területe akkor tartozik az egyik játékoshoz, ha a vele szomszédos összes nemüres rácsponton az adott játékos köve áll. A játékos pontszáma az általa birtokolt területeken lévő üres rácspontok számának összege.
Az ábrán egy $ 9 \times 9$-e Go-tábla látható. A fekete pontjait adó mezőkön "B", a fehérén "W" látható. A semleges mezőkön nincs betűjel.
A játékot fehér nyerte 21 − 3 = 18 ponttal.
Feladat
Írj programot, ami a tábla ismeretében megadja, hogy melyik játékos nyert, és azt is, hogy hány ponttal.
Bemenet
A bemenet több tesztesetet tartalmaz, minden teszteset három sorból áll, és az inputot egy egyetlen 0-t tartalmazó sor zárja le.
Egy teszteset első sora három számot ad meg, a tábla $n$ méretét, illetve a fekete és fehér kövek $b$ és $w$ számát.
($1\le n \le 19, 0\le b, 0\le w, 1\le b+w\le n^2 $)
Ezután a következő két sorban a fekete, majd a fehér kövek koordinátái következnek, "sor oszlop" párok formájában. Előfordulhat üres sor, ha valamelyik szín nem szerepel, de feltehetjük, hogy egy pozícióra legfeljebb egy kő kerül.
Egy teszteset első sora három számot ad meg, a tábla $n$ méretét, illetve a fekete és fehér kövek $b$ és $w$ számát.
($1\le n \le 19, 0\le b, 0\le w, 1\le b+w\le n^2 $)
Ezután a következő két sorban a fekete, majd a fehér kövek koordinátái következnek, "sor oszlop" párok formájában. Előfordulhat üres sor, ha valamelyik szín nem szerepel, de feltehetjük, hogy egy pozícióra legfeljebb egy kő kerül.
Kimenet
Minden kérdéshez adjuk meg, ki nyert és mennyivel. Például: "White wins by 12".
A döntetlen: "Draw".
Példa
| go.in | go.out |
| 1 1 0 1 1 2 0 1 1 1 5 12 4 1 1 1 2 1 3 2 1 2 3 3 1 3 3 4 1 4 3 5 1 5 2 5 3 1 4 2 4 3 4 3 5 0 | Draw White wins by 3 Black wins by 1 |