Surrounded Islands
You are given a two-dimensional integer matrix matrix containing 1s and 0s. 1 represents land and 0 represents water. An island is a group of 1s that are neighboring whose perimeter is surrounded by water. Return the number of completely surrounded islands.
Constraints
n, m ≤ 250wherenandmare the number of rows and columns inmatrix.
https://binarysearch.com/problems/Surrounded-Islands
ExamplesPermalink
Example 1Permalink
Input
- matrix =
[[1,1,0,0,0],
[0,0,0,0,0],
[0,1,1,1,0],
[0,1,0,1,0],
[0,1,1,1,0],
[0,0,0,0,0]]
Output
- answer =
1
Explanation
There’s 2 islands but only the middle island is completely surrounded.
SolutionPermalink
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| void setLandToZero(vector<vector<int>> &matrix, int i, int j) | |
| { | |
| if (i < 0 || i >= matrix.size() || j < 0 || j >= matrix[i].size()) | |
| { | |
| // out of bound | |
| return; | |
| } | |
| else if (matrix[i][j] == 0) | |
| { | |
| // not land | |
| return; | |
| } | |
| else | |
| { | |
| // expand | |
| matrix[i][j] = 0; | |
| setLandToZero(matrix, i - 1, j); | |
| setLandToZero(matrix, i + 1, j); | |
| setLandToZero(matrix, i, j - 1); | |
| setLandToZero(matrix, i, j + 1); | |
| } | |
| } | |
| int solve(vector<vector<int>> &matrix) | |
| { | |
| // idea is to set the land cells at the boundary and their | |
| // neighbours to zero | |
| // do this at the four edges of matrix | |
| int nRows = matrix.size(); | |
| int nCols = matrix[0].size(); | |
| // top and bottom row | |
| for (int r : {0, nRows - 1}) | |
| for (int c = 0; c < nCols; c++) | |
| setLandToZero(matrix, r, c); | |
| // left and right col | |
| for (int c : {0, nCols - 1}) | |
| for (int r = 0; r < nRows; r++) | |
| setLandToZero(matrix, r, c); | |
| // answer is the number of remaining islands | |
| int res = 0; | |
| for (int r = 0; r < nRows; r++) | |
| for (int c = 0; c < nCols; c++) | |
| if (matrix[r][c] == 1) | |
| { | |
| res++; | |
| setLandToZero(matrix, r, c); | |
| } | |
| return res; | |
| } |
Leave a comment