시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 4 | 1 | 1 | 50.000% |
Go is an ancient board game for two players that originated in China over 2,000 years ago. The game is notably known for being rich in strategy despite its relatively simple rules.
The game is played by two players who alternately place black and white stones on the vacant intersections of a grid of N × N orthogonal lines. The objective of the game is to use one’s stones to make a larger territory than the opponent.
The horizontal lines are numbered from top to bottom by the numbers from 1 to N, and the vertical lines are numbered from left to right by the numbers from 1 to N.
Two intersections or stones are adjacent if one of them is adjacent to the other, from right, left, top or bottom. A “solidly connected group” is a set of intersections or stones in which every pair is connected by a path of adjacent intersections or stones from the same set.
A solidly connected group of empty intersections or stones is called surrounded by a color, if all the adjacent intersections to the group are occupied by stones of that color.
A player’s territory consists of all the intersections occupied by the player’s stones, in addition to the solidly connected groups of empty intersections surrounded by the player’s stone color.
Here is a list of the rules for a simplified version of the game:
You are given the size of the board and a sequence of moves, and your task is to validate this sequence of moves and print the index (1-based) of the first invalid move (a move is invalid if the player is trying to put a stone in a non-empty intersection). If all moves are valid you should print the sizes of the territories for each player after the last move.
Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 ≤ T ≤ 100). After that follow the specifications of T test cases.
Each test case is specified on S + 1 lines. The first line contains two integers N and S representing the size of the board and the number of moves to validate, respectively (1 ≤ N ≤ 20, 1 ≤ S ≤ 1, 000). Each line of the remaining S lines will contain either two zeros which means a pass turn, or two integers R and C specifying the horizontal and vertical line numbers of the player’s move (1 ≤ R, C ≤ N).
For each test case, output, on a single line, one of two outputs:
3 4 4 1 1 2 2 3 3 4 4 4 5 1 2 1 1 2 1 1 1 2 2 4 8 1 2 1 1 0 0 0 0 2 2 2 1 4 4 1 1
2 2 16 0 Invalid 6
Explanation for the second test case