N Knights Problem
All submissions for this problem are available.
Dave recently mastered the problem of placing N queens on a chessboard so
that no two queens attack eachother.
Now he wants to see how many knights he can place on a chessboard so
that no two knights attack eachother.
Normally this would be a simple task, but some of the squares of the
chessboard have been marked as unusable and hence cannot have a knight placed
Recall that a knight can attack another knight if their vertical distance
is 2 and their horizontal distance is 1, or if their vertical distance is 1 and
their horizontal distance is 2. Only one knight may be placed on each square
of the chessboard
The first line of input contains an integer T (0<T≤50), the number of test cases to follow.
Each test case will begin with a line containing 2 integers M and N (0<M,N≤30),
denoting the number of rows and columns, respectively.
M lines follow, each containing exactly N characters.
The j-th character of the i-th line is '.' if a knight may be placed in the j-th column of the i-th
row, and '#' if the square is unusable.
For each test case, output on a single line the maximum number of knights that may be placed
on the chessboard such that no two attack eachother.
2 2 4 .... .... 5 5 ..#.. #..#. ##... ...## .....
The following image represents the chessboard and a possible solution to the second test case:
|Tags||cook04, medium, pieguy|
|Time Limit:||0.294118 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TEXT|
Fetching successful submissions
If you are still having problems, see a sample solution here.