Given a boolean 2D matrix, find the number of islands.
Notice
0 is represented as the sea, 1 is represented as the island. If two 1 is adjacent, we consider them in the same island. We only consider up/down/left/right adjacent.
Have you met this question in a real interview?
Yes
Example
Given graph:
[
[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[0, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 1]
]
return 3.
LeetCode上的原题，请参见我之前的博客Number of Islands。
class Solution {
public:
/**
* @param grid a boolean 2D matrix
* @return an integer
*/
int numIslands(vector<vector<bool>>& grid) {
if (grid.empty() || grid[].empty()) return ;
int m = grid.size(), n = grid[].size(), res = ;
vector<vector<bool>> visited(m, vector<bool>(n, false));
for (int i = ; i < m; ++i) {
for (int j = ; j < n; ++j) {
if (grid[i][j] && !visited[i][j]) {
helper(grid, visited, i, j);
++res;
}
}
}
return res;
}
void helper(vector<vector<bool>>& grid, vector<vector<bool>>& visited, int i, int j) {
int m = grid.size(), n = grid[].size();
if (i < || i >= m || j < || j >= n || !grid[i][j] || visited[i][j]) return;
visited[i][j] = true;
helper(grid, visited, i + , j);
helper(grid, visited, i - , j);
helper(grid, visited, i, j + );
helper(grid, visited, i, j - );
}
};