All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.Forking is an important tactics in the game of chess. A piece is said to perform a fork if
1) It is on a safe square, i.e., the next move by the opponent does not kill the piece
2) It targets atleast 2 of the opponents pieces in its next move. So even if the opponent moves one of his pieces to safety, one of his remaining pieces can be killed.
You are given an NxN board, containing M White Queens. Remember, a Queen can move vertically, horizontally and diagonally; and kills any opponents piece directly in these directions. A Knight has 8 possible moves from position (i,j), viz (i+1,j+2), (i+1,j-2), (i-1,j+2), (i-1,j-2), (i+2,j+1), (i+2,j-1), (i-2,j+1), (i-2,j-1) (while remaining inside the NxN board). You have to find out the number of unoccupied positions on the NxN board, where a Black Knight can be placed such that it forks atleast 2 Queens.
First line contains T, number of testcases
Each testcase starts with a line containing two integers N and M
Then M lines follow, ith line containing two space separated integers X[i] and Y[i], the coordinates of the ith Queen
For each testcase, output a single line containing the answer to the question
40 points : 1<=N<=8
60 points : 1<=N<=1000
No two queens can be in the same square.
Only forking position is (2,3)
|Tags||brute-force, ltime11, piyushkumar, simple|
|Time Limit:||1 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, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.