King Placement

Moderate

0/80

Average time to solve is 40m

Contributed by

0 upvote

Asked in company

Problem statement

This is a typical chess game where your opponent first places a random number of Knights, Rooks, Bishop, and Queens on an ‘N*N’ chessboard, and then you have to place your king safely on the chessboard such that it should not be under attack by any piece.

Given an ‘N*N’ chessboard with ‘K’ number of Knights, ‘R’ number of Rooks, ‘B’ number of Bishops, and ‘Q’ number of queens. Your task is to find out the number of squares on the chessboard such that your King is not checked by any of your opponent's pieces.

NOTE: If you don't know how to play chess and how chess pieces move, please refer to the below link (you can concentrate only on how the above-mentioned pieces move).

HOW TO PLAY CHESS

EXAMPLE :

Refer to the explanation of Sample Input 1 for better understanding.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line will contain the integer 'T', the number of test cases.

The first line of each test case consists of integer  'N', the length of the given chessboard.

The next line contains ‘K’, no. of Knights. Next, ‘K’ lines provide 2 space-separated integers denoting the row and the column of the Knights ‘(i,j)’

The next line contains ‘R’, no. of Rooks. Next, ‘R’ lines provide 2 space-separated integers denoting the row and the column of the Rooks ‘(i,j)’

The next line contains ‘B’, no. of Bishops. Next, ‘B’ lines provide 2 space-separated integers denoting the row and the column of the Bishops ‘(i,j)’

The next line contains ‘Q’, no. of Queens. Next, ‘Q’ lines provide 2 space-separated integers denoting the row and the column of the Queens ‘(i,j)’

Output format :

For each test case, print the number of squares where King can be placed safely.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= 'T' <= 10
2 <= 'N' <= 100
0 <= 'K' + ‘R’ + ‘B’ + ‘Q’ <= ‘N * N’
0 <= ‘i’, ‘j’ <= ‘N - 1’
It is guaranteed that sum of ‘N’ over all test cases is <= 1000
Time Limit: 1 sec

Sample Input 1 :

Sample Output 1 :

2
5

Explanation Of Sample Input 1 :

For the first test case,

The safe places are (0, 1) and (1, 0)

Hence, the output will be: 2

For the second test case,

The safe places are (0, 1), (0, 3), (1, 7), (3, 1), and (5, 7).

Hence, the output will be: 5

Sample Input 2 :

Sample Output 2 :

0
6

Console