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.
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[0].empty()) return 0; int m = grid.size(), n = grid[0].size(), res = 0; vector<vector<bool>> visited(m, vector<bool>(n, false)); for (int i = 0; i < m; ++i) { for (int j = 0; 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[0].size(); if (i < 0 || i >= m || j < 0 || j >= n || !grid[i][j] || visited[i][j]) return; visited[i][j] = true; helper(grid, visited, i + 1, j); helper(grid, visited, i - 1, j); helper(grid, visited, i, j + 1); helper(grid, visited, i, j - 1); } };
本文转自博客园Grandyang的博客，原文链接：岛屿的数量[LintCode] Number of Islands ，如需转载请自行联系原博主。
![[leetcode/lintcode 题解] 阿里算法面试真题：丑数 II · Ugly Number II](https://ucc.alicdn.com/pic/developer-ecology/6cff28c30bac45cda8393adfc820bcb6.png?x-oss-process=image/resize,h_160,m_lfit)
