IX Wiosenny Turniej w Programowaniu Zespołowym Politechnika Poznańska, 11.06.2005

Opis

W Patentolandii co roku odbywają się najróżniejsze turnieje logiczne. W każdym z nich zarówno Anty-Patentowcy jak i Anty-Anty-Patentowcy wystawiają swoje drużyny, walcząc o tytuły najlepszych, najsprytniejszych, najinteligentniejszych i jeszcze wielu innych. Ponieważ wielokrotnie uczestnicy korzystali z pomocy szybkich komputerów i swoich wspaniałych, opatentowanych lub nie, algorytmów, w tym roku postanowiono wybrać grę, w której szybkie komputery nie pomogą uczestnikom.

Po dyskusjach wybór padł na grę planszową Go. W Go dwóch graczy naprzemiennie ustawia białe i czarne kamienie na przecięciach planszy, w celu otoczenia większego terytorium (części planszy) niż przeciwnik. Każde przecięcie planszy otoczone przez kamienie jednego koloru liczą się jako punkt. Szybko rozpoczęto rozgrywki i oczywiście okazało się, że część Anty-Anty-Patentowców postanowiła skorzystać z pomocy komputerów i swoich zdolności programistycznych, ale tymi osobami nie musimy się przejmować, gdyż odpadły zaraz w pierwszej rundzie. Anty-Patentowcy w grze korzystali z własnych umiejętności, ale szybko doszli do wniosku, że liczenie punktów na dużej planszy jest kłopotliwe i postanowili to zautomatyzować.

Zadanie

• Gra toczy się na planszy o wymiarach NxN przecięć.
  
• Na każdym przecięciu może znajdować się kamień biały, kamień czarny lub przecięcie może być puste.
  
• Przecięcia (i kamienie) sąsiadują ze sobą w poziomie i pionie.
  
• Każde puste przecięcie jest liczone jako punkt terytorium, jeżeli posuwając się po sąsiadujących, pustych polach, można dojść tylko do otaczających je kamieni jednego koloru, lub brzegu planszy.
  Przykład na obrazku: trójkątami zaznaczone są punktu czarnego gracza, natomiast kwadratami punkty białego gracza.
  
• Jeżeli z pustego przecięcia da dojść się zarówno do białych jak i do czarnych kamieni to takie przecięcie nazywamy Dame - na obrazku zaznaczone okręgami.
  
• Wszystkie kamienie jednego koloru, które sąsiadują ze sobą, jak i terytorium które otaczają nazywamy grupą. Jeżeli grupa sąsiaduje z co najmniej jednym punktem Dame to terytorium otoczone przez tą grupę nie jest liczone do punktów.
  
• Do otoczonego terytorium dodaje się zbitych podczas gry jeńców. Ponieważ grę zaczyna czarny, i ma dzięki temu większe szanse na wygraną, biały dostaje dodatkowo 6,5 punktów Komi. Dzięki temu szanse są wyrównane oraz gra nie może zakończyć się remisem.

Wejście

W pierwszej linii wejścia znajduje się jedna dodatnia liczba całkowita, oznaczająca liczbę następujących zestawów danych.

W pierwszej linii każdego zestawu znajdują się trzy liczby całkowite: 5≤N≤1000, 0≤=B,C≤10000, oznaczające odpowiednio: rozmiar planszy, liczbę jeńców zbitych przez czarnego, liczbę jeńców zbitych przez białego.
W kolejnych N liniach znajduje się kolejne linie planszy. W każdej linii znajduje się N znaków - 'C', 'B' i '*' opisujących planszę. C - oznacza kamień czarny, B - kamień biały, natomiast * oznacza puste przecięcie.

Wyjście

Dla każdego zestawu należy wypisać jedną liczbę, będącą liczbą punktów białego: (liczba punktów białego na planszy) - (liczba punktów czarnego na planszy) + (liczba jeńców zbitych przez białego) - (liczba jeńców zbitych przez czarnego) + 6,5.

Przykładowe wejście

1
13 3 6
***CB**BC****
***CB**BC*CC*
**CBBBBBC**C*
**CCCCCBBCCC*
**CBBBCCBC*CC
**CB**BCBC***
***CB*BCCBBBB
***CB**BCB***
**CBB**BCCB**
**CBB***BCB**
**CCCBB*BCB**
*****CB*BCB**
*****CB*BCB**

Przykładowe wyjście

-9.5