King Placement

Moderate
0/80
Average time to solve is 40m
profile
Contributed by
0 upvote

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.

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 :
2

4
2
0 0
1 1
1
2 2
0
1
3 3

8
4
2 6
3 2
5 6
7 7
4
2 2
4 6
6 4
7 5
4
0 4
1 1
1 6
5 1
2
3 5
6 0
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 :
2

4
2
0 0
1 1
3
2 2
3 0
0 3
0
1
3 3

8
5
2 6
3 2
5 6
7 7
4 0
4
2 2
4 6
6 4
7 5
4
0 4
1 1
1 6
5 1
3
3 5
6 0
4 2
Sample Output 2 :
0
6
Hint

Can we try to place our king at each position and check if it is attacked.

Approaches (2)
Brute Force

The idea of this approach is to place the king at each cell that is not occupied and check if it is getting attacked by any chess piece.

 

So we would iterate on each cell of the chessboard and if let’s suppose we are currently at cell (i, j) then 

  • If there is a rook or queen in this row or column and there is no other chess piece in between, we can’t place the king here.
  • If there is a queen or bishop in the same main diagonal or opposite diagonal of the chessboard and there is no other chess piece in between, we can’t place the king here.
  • If there is a knight at ‘L-shape’ from this cell, we can’t place the king here.

 

If all the above conditions are false then we can place the king here safely.

 

Algorithm:
 

// The function will check if there is a knight attacking the given cell.

Bool attackedByKnight(i, j)

  • If ‘(i-2,j-1)’ is inside the chessboard and a knight is present there return ‘true’
  • If ‘(i-2,j+1)’ is inside the chessboard and a knight is present there return ‘true’
  • If ‘(i+2,j-1)’ is inside the chessboard and a knight is present there return ‘true’
  • If ‘(i+2,j+1)’ is inside the chessboard and a knight is present there return ‘true’
  • If ‘(i-1,j-2)’ is inside the chessboard and a knight is present there return ‘true’
  • If ‘(i+1,j-2)’ is inside the chessboard and a knight is present there return ‘true’
  • If ‘(i-1,j+2)’ is inside the chessboard and a knight is present there return ‘true’
  • If ‘(i+1,j+2)’ is inside the chessboard and a knight is present there return ‘true’
  • Return ‘false’

Bool attackedFromLeft(i, j)

  • Initialize variables ‘x’ and ‘y’ with initial values ‘i’ and ‘j-1’ respectively.
  • Run a while loop until ‘(x, y)’ is inside the chessboard
    • If cell ‘(x, y)’ is empty then decrement ‘y’ by one.
    • Else If cell ‘(x, y)’ have a rook or queen then return ‘true’
    • Else return ‘false’
  • Return ‘false’

Bool attackedFromRight(i, j)

  • Initialize variables ‘x’ and ‘y’ with initial values ‘i’ and ‘j+1’ respectively.
  • Run a while loop until ‘(x, y)’ is inside the chessboard
    • If cell ‘(x, y)’ is empty then increment ‘y’ by one.
    • Else If cell ‘(x, y)’ have a rook or queen then return ‘true’
    • Else return ‘false’
  • Return ‘false’
     

Bool attackedFromUp(i, j)

  • Initialize variables ‘x’ and ‘y’ with initial values ‘i-1’ and ‘j’ respectively.
  • Run a while loop until ‘(x, y)’ is inside the chessboard
    • If cell ‘(x, y)’ is empty then decrement ‘x’ by one.
    • Else If cell ‘(x, y)’ have a rook or queen then return ‘true’
    • Else return ‘false’
  • Return ‘false’

Bool attackedFromDown(i, j)

  • Initialize variables ‘x’ and ‘y’ with initial values ‘i+1’ and ‘j’ respectively.
  • Run a while loop until ‘(x, y)’ is inside the chessboard
    • If cell ‘(x, y)’ is empty then increment ‘x’ by one.
    • Else If cell ‘(x, y)’ have a rook or queen then return ‘true’
    • Else return ‘false’
  • Return ‘false’

Bool attackedFromMainDiagonalUp(i, j)

  • Initialize variables ‘x’ and ‘y’ with initial values ‘i-1’ and ‘j-1’ respectively.
  • Run a while loop until ‘(x, y)’ is inside the chessboard
    • If cell ‘(x, y)’ is empty then decrement ‘x’ and ‘y’ by one.
    • Else If cell ‘(x, y)’ have a bishop or queen then return ‘true’
    • Else return ‘false’
  • Return ‘false’

Bool attackedFromMainDiagonalDown(i, j)

  • Initialize variables ‘x’ and ‘y’ with initial values ‘i+1’ and ‘j+1’ respectively.
  • Run a while loop until ‘(x, y)’ is inside the chessboard
    • If cell ‘(x, y)’ is empty then increment ‘x’ and ‘y’ by one.
    • Else If cell ‘(x, y)’ have a bishop or queen then return ‘true’
    • Else return ‘false’
  • Return ‘false’

Bool attackedFromOtherDiagonalUp(i, j)

  • Initialize variables ‘x’ and ‘y’ with initial values ‘i-1’ and ‘j+1’ respectively.
  • Run a while loop until ‘(x, y)’ is inside the chessboard
    • If cell ‘(x, y)’ is empty then decrement ‘x’ by one and increment ‘y’ by one.
    • Else If cell ‘(x, y)’ have a bishop or queen then return ‘true’
    • Else return ‘false’
  • Return ‘false’

Bool attackedFromOtherDiagonalDown(i, j)

  • Initialize variables ‘x’ and ‘y’ with initial values ‘i+1’ and ‘j-1’ respectively.
  • Run a while loop until ‘(x, y)’ is inside the chessboard
    • If cell ‘(x, y)’ is empty then increment ‘x’ by one and decrement ‘y’ by one.
    • Else If cell ‘(x, y)’ have a bishop or queen then return ‘true’
    • Else return ‘false’
  • Return ‘false’
     

Bool attackedByAny(i, j)

  • If ‘attackedByKnight(i, j)’ is true then return ‘true’
  • If ‘attackedFromLeft(i, j)’ is true then return ‘true’
  • If ‘attackedFromRight(i, j)’ is true then return ‘true’
  • If ‘attackedFromUp(i, j)’ is true then return ‘true’
  • If ‘attackedFromDown(i, j)’ is true then return ‘true’
  • If ‘attackedFromMainDiagonalUp(i, j)’ is true then return ‘true’
  • If ‘attackedFromMainDiagonalDown(i, j)’ is true then return ‘true’
  • If ‘attackedFromOtherDiagonalUp(i, j)’ is true then return ‘true’
  • If ‘attackedFromOtherDiagonalDown(i, j)’ is true then return ‘true’
  • Return ‘false’

 

// The function will return the count of safe positions to place the king on the chessboard.

Int kingPlacement(N, K, R, B, Q, pointsK[], pointsR[], pointsB[], pointsQ[])

  • Initialize variable name ‘ans’ with initial value zero.
  • Initialize 2D character array ‘matrix’ of size ‘N * N’ with initial value ‘.’ denoting every cell is empty.
  • Run a loop from 0 to ‘K-1’ with a variable ‘i’
    • Mark ‘pointK[i]’ as character K in ‘matrix’.
  • Run a loop from 0 to ‘R-1’ with a variable ‘i’
    • Mark ‘pointR[i]’ as character R in ‘matrix’.
  • Run a loop from 0 to ‘B-1’ with a variable ‘i’
    • Mark ‘pointB[i]’ as character B in ‘matrix’.
  • Run a loop from 0 to ‘Q-1’ with a variable ‘i’
    • Mark ‘pointQ[i]’ as character Q in ‘matrix’.
  • Run a loop from 0 to ‘N-1’ with a variable ‘i’
    • Run a loop from 0 to ‘N-1’ with a variable ‘j’
      • If ‘matrix[i][j]’ is empty and ‘attackedByAny(i, j)’ is false then increment ‘ans’ by one.
  • Return ‘ans’
Time Complexity

O(N * N * N), Where ‘N’ is the input integer.
 

The time complexity to check if any cell is attacked by any chess piece is O(N) as we check on each side, and we iterated through each cell once, hence the time complexity will be O(N * N * N).

Space Complexity

O(N * N), Where ‘N’ is the input integer.
 

As we used a 2D character array of size ‘N * N’ to mark the chess piece's presence on the chessboard, hence the space complexity will be O(N * N).

Code Solution
(100% EXP penalty)
King Placement
Full screen
Console