The first line contains an integer ‘T’ denoting the number of test cases.
The first input line of each test case contains two single space-separated integers ‘N’ and ‘M’ representing the number of rows and columns of the grid, respectively.
The second line of each test case contains an integer ‘Q’ representing the number of queries.
Next ‘Q’ lines contain two single space-separated integers ‘X’ and ‘Y’, representing the coordinates of the grid i.e the coordinates of the point to be turned into land.
For each test case, print a single integer denoting the number of islands after each query operation.
Print the output of each test case in a separate line.
You are not required to print the expected output; it has already been taken care of. Just implement the given function.
1 <= T <= 5
1 <= N <= 1000
1 <= M <= 1000
1 <= Q <= 100000
0 <= X < N
0 <= Y < M
Time limit: 1 sec
The idea here is to represent the grid as a graph and all the adjacent land cells are connected via an edge. Finally, do DFS on the grid and find the number of connected components after each query operation.
The algorithm is as follows:
The idea here is to use the union-find data structure to efficiently count the number of connected components in the grid. For each query, we will union the given land position with all the neighboring lands. Creating land increases the 'NUMBEROFISLANDS' by 1. But if we connect two different islands together it decreases the 'NUMBEROFISLANDS' by 1.
The algorithm is as follows:
Good Bad Graph
Good Bad Graph
Ninja and the experiment
COUNT ISLANDS
Search In A Sorted 2D Matrix
Spiral Matrix
Spiral Matrix
Spiral Matrix