Given a binary matrix mat[][] of dimensions NxM such that 1 denotes land and 0 denotes water. Find the number of closed islands in the given matrix.
Note: A closed island is a group of 1s surrounded by only 0s on all the boundaries (except diagonals). In simple words, a closed island is an island whose none of the 1s lie on the edges of the matrix.
Example 1:
Input:
N = 5, M = 8
mat[][] = {{0, 0, 0, 0, 0, 0, 0, 1},
{0, 1, 1, 1, 1, 0, 0, 1},
{0, 1, 0, 1, 0, 0, 0, 1},
{0, 1, 1, 1, 1, 0, 1, 0},
{1, 0, 0, 0, 0, 1, 0, 1}}
Output:
2
Explanation:
mat[][] = {{0, 0, 0, 0, 0, 0, 0, 1},
{0, 1, 1, 1, 1, 0, 0, 1},
{0, 1, 0, 1, 0, 0, 0, 1},
{0, 1, 1, 1, 1, 0, 1, 0},
{1, 0, 0, 0, 0, 1, 0, 1}}
There are 2 closed islands. The islands in dark are closed because they are completely surrounded by 0s (water). There are two more islands in the last column of the matrix, but they are not completely surrounded by 0s. Hence they are not closed islands.
Example 2:
Input:
N = 3, M = 3
mat[][] = {{1, 0, 0},
{0, 1, 0},
{0, 0, 1}}
Output:
1
Explanation:
mat[][] = {{1, 0, 0},
{0, 1, 0},
{0, 0, 1}}
There is just a one closed island.
Your task:
You dont need to read input or print anything. Your task is to complete the function closedIslands() which takes two integers N and M, and a 2D binary matrix mat as input parameters and returns the number of closed islands.
Expected Time Complexity: O(NM)
Expected Auxiliary Space: O(NM)
Constraints:
1 ≤ N,M ≤ 500

见题面

见题面