Last Updated: 5 Jan, 2021

Rooks Placing

Moderate

Asked in companies

Solve now

Problem statement

You are given an n×n chessboard. Rows and columns of the board are numbered from 0 to ‘n’-1. Cell (r,c) lies at the intersection of row number 'r' and column number ‘c’.

Rook is a chess piece that can in one turn move any number of cells vertically or horizontally. There are ‘m’ rooks (m<=n) placed on the chessboard in such a way that no pair of rooks attack each other. I.e. there are no pairs of rooks that share a common row or a column.

You are given the position of the ‘m’ rooks that are already placed on the chessboard. Your task is to find the maximum number of additional rooks with their positions that can be placed on the given chessboard such that no rook attacks some other rook. Print the positions (cells) of these additional rooks in lexicographical order. If there are multiple ways of placing the maximum number of additional rooks, you should find one that gives the lexicographically smallest sequence of cells after arranging their cells in lexicographical order.

Note :

In lexicographical order, cell (a, b) comes before cell (c, d), if either a < c  or (a = c and b < d).

Input Format :

The first line of input contains an integer ‘T’ denoting the number of test cases. The description of  ‘T’ test cases follows.

The first line of each test case contains two space-separated integers ‘n’ and ‘m’ representing dimensions of the chessboard and the number of rooks that are already present in the chessboard respectively.

Then ‘m’ line follows, each containing 2 space-separated integers ‘r’, ‘c’ representing that there is a rook at cell (r, c).

Output Format :

For each test case, print in one line an integer ‘k’ representing the maximum number of additional rooks that can be placed on the chessboard and then print ‘k’ lines each of which contains 2 space-separated integers ‘r’ and ‘c’ representing that a rook is placed at cell (r, c). You need to print these cells in lexicographical order.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 50
1 <= n <= 10^4
0 <= m <= n
0 <= r, c < n

Where ‘T’ is the number of test cases and ‘n’ is the dimensions of the chessboard, ‘m’ is the number of rooks that are already present on the chessboard, and (r, c) represents the cell of the chessboard.

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Create a boolean matrix of order n * n. Initially, all the cells of the matrix will be false.
Iterate over the given array having positions of already placed rooks, and for each rook at cell (r, c) mark true at cell (r, c) in the boolean matrix.
Create a vector of arrays to store the positions of the additional rooks. Let's name it ‘result’.
Run a nested loop where the outer loop ‘i’ ranges from 0 to n-1 and the inner loop ‘j’ ranges from 0 to n-1, and for each pair (i, j) do the following:
- If the value in the boolean matrix at cell (i, j) is true then we cannot place rook at the cell (i, j).
- Otherwise, run a loop where ‘k’ ranges from 0 to n-1, and for each ‘k’ check whether there exists any cell (i, k) or (k, j) which has the value true in the boolean matrix. If no such cell exists then mark (i, j) true in the boolean matrix and appends the cell (i, j) in the vector ‘result’.
Return ‘result’, it will now have the position of additional rooks in lexicographical order and its size is maximum possible.

Solve now

02 Approach

Create two boolean arrays ‘rows’, ‘cols’ of size ‘n’. Initially fill both of these arrays by boolean false. The ‘rows[i]’ will be true if there exist rooks at ‘i’th row, similarly ‘cols[i]’ will be true if there exist rooks at ‘ith’ column.
Iterate over the given array having positions of already placed rooks, and for each rook at cell (r, c) assign ‘rows[r]’:= true and ‘cols[c]’:= true.
Create a vector of arrays to store the positions of the additional rooks. Let's name it ‘result’.
Run a nested loop where the outer loop ‘i’ ranges from 0 to n-1 and the inner loop ‘j’ ranges from 0 to n-1, and for each pair (i, j) do the following:
- If the value of ‘rows[i]’ is true, or the value of ‘cols[j]’ is true then you cannot place a rook at the cell (i, j).
- Otherwise, assign ‘rows[i]’:= true and ‘cols[j]’ := false, and appends cell (i, j) in the vector ‘result'.
Return ‘result’, it will now have the position of additional rooks in lexicographical order and its size is maximum possible.

Solve now

03 Approach

We can observe that if a rook is placed at cell (r, c), then no other rook can be placed in any cell of row ‘r’ and column ‘c’, This approach is based on the idea that a maximum of (n – m) rooks can be placed on the chessboard according to the Pigeonhole Principle. Below are the steps:

Create two boolean arrays ‘rows’, ‘cols’ of size ‘n’. Initially fill both of these arrays by boolean false. The ‘rows[i]’ will be true if there exist rooks at ‘i’th row, similarly ‘cols[i]’ will be true if there exist rooks at ‘ith’ column.
Iterate over the given array having positions of already placed rooks, and for each rook at cell (r, c) assign ‘rows[r]’:= true and ‘cols[c]’:= true.
The maximum number of additional rooks that can be placed will be ‘n - m’, where ‘n’ is dimensions of the chessboard and ‘m’ is the number of rooks already placed on the chessboard.
Create a matrix of dimension (n-m)*2 to store positions of the additional rooks. Let's name it ‘result’.
Create two integer arrays ‘freeRows’ and ‘freeCols’ of size ‘n-m’, It will keep the row number and column number in increasing order of those rows and columns where rook is not already present.
Run a loop where ‘i’ ranges from 0 to n-1 and for each ‘i’ if ‘rows[i]’:= false, then add ‘i’ to ‘freeRows’ or if ‘cols[i]’:= false, then add ‘i’ to ‘freeCols’.
Run a loop where ‘i’ ranges from 0 to n-m-1 and for each ‘i’ add ‘freeRows[i]’ and ‘freeCols[i]’ at index ‘i’ of the ‘result’ matrix.
Return ‘result’, it will now have the position of additional rooks in lexicographical order and its size is maximum possible.

Solve now