Last Updated: 13 Nov, 2021

Matrix Illumination

Hard

Asked in companies

Solve now

Problem statement

A 2-D matrix ‘MAT’ of size ‘N’ * ‘N’ is present, where each cell consists of a bulb. Initially, all bulbs are turned OFF. You are given a 2-D array ‘BULB’ of size ‘M’, where ‘BULB[i]’ = [‘ROW’, ‘COL’] indicates that the bulb is turned ON at position [‘ROW’, ‘COL’]. When a bulb is turned ON, it illuminates its cell and illuminates the cells present in the same row, column, or diagonal.

You are also given another 2-D array, ‘QUERY’, where ‘QUERY[i]’ = [‘ROW’, ‘COL’]. For each query, print ‘1’ if the ‘MAT[ROW][COL]’ is illuminated, else print 0. After answering a query, you have to turn OFF the bulb at ‘MAT[ROW][COL]’ and its 8 adjacent bulbs if they exist. A bulb is adjacent if it shares either a side or corner with ‘MAT[ROW][COL]’.

Note: There can be repeated values present in the ‘BULB’ array. If the same value is repeated in the ‘BULB’ array, the ‘BULB’ remains on.

For example:

Initially, let ‘MAT’ be : 
0 0 0
0 0 0
0 0 0
Let the ‘BULB’ array be: [[0, 0]]

‘MAT’ will be changed to :
‘1’ 1 1
1 1 0
1 0 1    where (1 represents the cell is illuminated and ‘1’ represents the cell is illuminated and the bulb is turned ON).

Let ‘QUERY’ array be : [[0, 1]]
As the cell [0, 1] is illuminated, we will print 1 and then turn OFF the bulb at that position and adjacent to it.

‘MAT’ will be changed to :
0 0 0
0 0 0
0 0 0

Input Format :

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

The first line of each test case contains two space-separated integers, ‘N’, ‘M’, and ‘Q’, representing the size of the matrix, the size of the ‘BULB’ array, and the size of the ‘QUERY’ array.

The next ‘M’  lines of each test case contain two space-separated integers representing the ‘BULB’ array elements.

The next ‘Q’  lines of each test case contain two space-separated integers representing the ‘QUERY’ array elements.

Output Format :

For each test case, print the result of queries in 0 and 1, where 0 represents the cell is not illuminated, and 1 represents the cell is illuminated.

Print output of each test case in a separate line.

Note :

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

Constraints :

1 <= T <= 10
1 <= M, N, Q <= 2*10^4
0 <= BULB[i][0], BULB[i][1], QUERY[i][0], QUERY[i][1] < N    

Time Limit: 1 sec

Solve now

Approaches

01 Approach

The basic idea is to simply check every row, column, and diagonal from which a cell can be illuminated for each query. For each cell, there can be 1 row, 1 column, and four diagonals from which it can be illuminated. So we simply check whether a bulb is ON or not in these. We use a set to store the positions of the bulbs that are already ON.

Here is the algorithm :

Create a set (say, ‘S’) to store the bulbs which are turned ON.
Run a loop from 0 to ‘M’ (say, iterator ‘i’) to traverse the ‘BULB’ array.
- Insert the current position in the set.
Create an array (say, ‘ANS’) to store the result.
Run a loop from 0 to ‘Q’ (say, iterator ‘i’) to run each query.
- Call the function CHECK that will tell whether the current cell can be illuminated or not.
- If the current cell can be illuminated
  - Push 1 in ‘ANS’.
  - Remove the bulbs from the set that are ON and adjacent to the current cell.
- Else,
  - Push 0 in ‘ANS’.
Return ‘ANS’.

CHECK(‘N’, ‘S’, ‘R’, ‘C’) (where ‘N’ is the size of the matrix, ‘S’ is the set that consists of positions where the bulb is ON, ‘R’ and ‘C’ is the position of the current query).

Run a loop from 0 to ‘N’ (say, iterator ‘i’)
- Check if position [‘R’, ‘i’] is present in the set.
  - Return TRUE.
Run a loop from 0 to ‘N’ (say, iterator ‘i’)
- Check if position [‘i’, ‘C’] is present in the set.
  - Return TRUE.
Create two variables (say, ‘diagR’ and ‘diagC’) to traverse the diagonals.
Run a loop till ‘diagR’ and ‘diagC’ are greater than equal to 0.
- Check if position [‘digaR’, ‘diagC’] is present in the set.
  - Return TRUE.
Similarly, check for all the other diagonals.
Finally, return FALSE.

Solve now

02 Approach

The basic idea is to store the count of rows and columns from which a cell can be illuminated. We store these values for each cell. We also store the count of diagonals from which a cell can be illuminated. And for each query, we check whether any of the rows, columns or diagonal for a cell have a count greater than 1, if it is, we print 1, else 0. After performing each query, we subtract the row, column, and diagonal count for that cell and its adjacent cells. We also use a set to store the bulbs, which are turned ON.

Here is the algorithm :

Create a set (say, ‘S’) to store the bulbs which are turned ON.
Create 4 unordered maps (say, ‘ROWS’, ‘COLS’, DIAG1’, and ‘DIAG2’) that will store the count of rows, columns, and diagonals illuminated for each cell.
Run a loop from 0 to ‘M’ (say, iterator ‘i’) to traverse the ‘BULB’ array.
- Check if the current position (say, ‘R’, ‘C’) is not present in the set.
  - Insert the current position in the set.
  - Increment ‘ROWS[R]’, ‘COLS[C]’, ‘DIAG1[R + C]’, ‘DIAG2[R - C]’ by 1.
Create an array (say, ‘ANS’) to store the result.
Run a loop from 0 to ‘Q’ (say, iterator ‘i’) to run each query.
- Check if ‘ROWS[R]’ or ‘COLS[C]’ or ‘DIAG1[R + C]’ or ‘DIAG2[R - C] is greater than 1.
  - Push 1 in ‘ANS’.
  - Run a loop for all adjacent positions (say, ‘adjR’ and ‘adjC’) to the current position (say ‘R’ and ‘C’).
    - Check if the ‘adjR’ and ‘adjC’ are present in ‘S’.
      - Remove the current position from set ‘S’ if present.
      - Remove the illumination from the current position by decrementing values of adjacent positions by 1 in each map.
- Else,
  - Push 0 in ‘ANS’.
Return ‘ANS’.

Solve now