Условие
Задача E. Fence
---
В играта Fence двама играчи се редуват да поставят червени и сини пулове върху шахматна дъска с изцяло бели полета и размери NxN. Всеки от тях се опитва да загради толкова територия (т.е. региони от незапълнени полета), колкото е възможно. В края на играта, резултатът на всеки играч е общата площ на териториите, които е успял да загради със своите пулове. Напишете програма, която изчислява резултата на всеки играч и определя победителя, ако е известно местоположението на червените и сините пулове върху игралната дъска в края на играта. Програмата трябва да може да обработва няколко групи тестови данни.
Например, на фигурата е показанa игрална дъска 9х9 и разположението на червените и сините пулове. С R1, R2, R3 са означени незаетите полета, които играчът с червените пулове е успял да загради. С B1, B2,…,B21 са означени незаетите полета, които играчът със сините пулове е успял да загради. Неозначени са незаетите полета, които са останали „свободни”. Сините пулове са заградили 21 полета, а червените -3 полета.
Две полета на игралната дъска с координати (x1, y1) и (x2, y2) са съседни, ако |x1-x2|+|y1-y2|=1
Дадена свързана област от незапълнени полета принадлежи към територията на един играч, ако всички съседни запълнени полета, принадлежат на този играч (виж фигурата). Резултатът на всеки от играчите се формира от общия брой на незаетите полета, които е успял да загради.
Вход
---
От първия ред на стандартния вход се въвежда броят на тестовите случаи. За всеки тест от първия ред се въвеждат три цели числа N, B и R. Числото N e размерът на игралната дъска, B е броя на сините пулове, разположени върху игралната дъска, R е броя на червените пулове, разположени върху игралната дъска. Вторият ред съдържа B двойки от цели числа x1 y1 ... xB yB (където 1 ≤ xi, yi ≤ N), които указват разположението на сините пулове върху игралната дъска. Третият ред съдържа R двойки от цели числа x1 y1 . . . xR yR (където 1 ≤ xi, yi ≤ N), които указват разположението на червените пулове върху игралната дъска. Гарантирано е, че не се допуска повече от един пул да заема дадено игрално поле.
Изход
---
За всеки тестов случай на единствен ред на стандартния изход да се изведе символен низ: "Bs:Rq", където s е цяло число равно на броя на полетата, заградени от сините пулове, а q е цяло число равно на броя на полетата, заградени от червените пулове.
Ограничения
---
1 ≤ N ≤ 19
B ≥ 0, R ≥ 0 и 1 ≤ B + R ≤ N2
Примерен вход
---
2
9 26 25
1 3 1 4 1 8 2 1 2 2 2 4 2 9 3 1 3 3 3 4 3 5 4 1 5 4
5 9 6 2 6 7 6 8 6 9 7 1 7 2 7 3 7 6 7 7 8 4 8 5 8 6
1 5 1 6 2 5 2 7 3 2 3 6 3 7 4 2 4 3 4 4 4 5 4 8 4 9
5 1 5 2 5 3 5 6 5 7 5 8 6 1 6 3 6 5 6 6 7 4 7 5
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
Примерен изход
---
B21:R3
B3:R2
« Предходна страница
Решение
Въпрос