Problem B
Atoms
Input: Standard Input
Output: Standard Output
Atoms is a two player game consisting of an N*N grid. The top-left cell has a
coordinate of (0, 0) and the
bottom-right has a coordinate of (N-1,N-1).
Each player has an infinite number of atoms
with them. Every atom of player one
has the same color. The atoms of
player two also have same color but they are different from those of player
one. The two players take turns to place atoms
on the grid. On each turn, a player selects a stable cell to place one atom
from his collection. The rule for stability
is simple; the cell must either be empty or it must already contain an atom of that player’s color. There is
however an upper limit to the number of atoms
a cell may contain and they are described below:
i)
The
four corner cells can contain at most 1 atom.
ii)
The
other outer cells can contain at most 2 atoms.
iii)
The
remaining cells can contain at most 3 atoms.
As an example, the
figure above shows a grid of 5 x 5. The filled cells can contain at most 1 atom
each. The stripped ones can contain at most 2 atoms each and the blank
ones can contain at most 3 atoms each.
When selecting a stable cell, the two players follow rather simple rules:
i)
First,
player one places an atom on a
randomly selected cell.
ii)
Player
two looks for a cell whose minimum distance from any cell occupied by atoms of player one is maximized. Here
distances between cells are measured as Manhattan distance. The Manhattan
distance between two cells is the sum of the absolute row difference and column
difference. For example, the Manhattan distance between (1, 5) and (4, 2) is
equal to (4-1) + (5-2) = 3 + 3 = 6.
iii)
In
case of multiple cells fulfilling the criteria of rule (ii), the cell with lowest row number is selected. If there is still
a tie, then the cell with lowest column number is selected.
iv)
Player one then follows a similar strategy to
that described in (ii) to place
another atom and the game continues
likewise.
If a player is
unable to make any valid move, then he is considered the loser and the game
stops there.
Your task in this problem is simple. Given a
state of the grid, you are to determine if this state is achievable if the
players follow the rules mentioned earlier.
Input
The first line of input will start
with a positive integer T<50,
where T denotes the number of test cases. Each case will begin with a
number N(3<=N<=7) which
denotes the size of the grid for that case. N lines will follow with N integers
on each line. The absolute value of these integers will be less than 107.
A positive integer means player one has placed atoms in the corresponding cell and negative integer means player
two placed atoms in the cell. The
number of atoms in a cell is denoted
by the absolute value of the cell.
Output
For each case, output the case number
first. If the given configuration is valid output “valid”, otherwise output
“invalid”. Look at the sample in/out for exact format.
Sample Input Output
for Sample Input
|
2 3 1 0 0 0 0 0 0 0 -1 3 2 0 0 0 0 0 |
Case 1: valid Case 2: invalid |
Problem
Setter: Shamim Hafiz
Special
Thanks: Sohel Hafiz