Number of Islands II

Hard

0/120

Average time to solve is 45m

Contributed by

23 upvotes

+4 more companies

Problem Statement

You have a 2D grid of ‘N’ rows and ‘M’ columns which are initially filled with water. You are given ‘Q’ queries each consisting of two integers ‘X’ and ‘Y’ and in each query operation, you have to turn the water at position (‘X’, ‘Y’) into a land. You are supposed to find the number of islands in the grid after each query.

An island is a group of lands surrounded by water horizontally, vertically, or diagonally.

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

Input Format:

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.

Output Format:

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.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 1000
1 <= M <= 1000
1 <= Q <= 100000
0 <= X < N
0 <= Y < M

Time limit: 1 sec

Sample Input 1:

Sample Output 1:

1 1 2 3
1 1 2 2

Explanation of Sample Output 1:

In test case 1, 

0.  000
    000
    000

1.  100
    000
    000

2.  110
    000
    000

 3. 110
    001
    000

 4. 110
    001
    100

So, the answer is 1, 1, 2, 3.

In test case 2,

0.  00000
    00000
    00000
    00000

1.  00000
    01000
    00000
    00000

2.  01000
    01000
    00000
    00000

 3. 01000
    01000
    00000
    00010

 4. 01000
    01000
    00000
    00011

So, the answer is 1, 1, 2, 2.

Sample Input 2:

Sample Output 2:

1 2
1

Explanation of Sample Output 2:

In test case 1, 

0.  00
    00

1.  10
    00

2.  10
    01

So, the answer is 1, 2.

In test case 2,

0.  0

1.  1

So, the answer is 1.

Console