# LintCode: Number of Islands

节点：所有1的位置

边：两个相邻的1的位置有一条边

BFS／DFS (DFS使用递归，代码较短)

选一个没标记的点，然后搜索，扩展4个邻居（如果有），直到不能扩展

每一次是一个连通分量

难点：标记节点——判重

C++

DFS

 1 class Solution {
2 public:
3     void help(vector<vector<bool>>& a, int x, int y) {
4         if ((x < 0) || (x >= a.size()) || (y < 0) || (y >= a[x].size()) || a[x][y] == false) {
5             return ;
6         }
7         a[x][y] = false;
8         help(a, x + 1, y);
9         help(a, x - 1, y);
10         help(a, x, y + 1);
11         help(a, x, y - 1);
12     }
13     /**
14      * @param grid a boolean 2D matrix
15      * @return an integer
16      */
17     int numIslands(vector<vector<bool>>& grid) {
18         // Write your code here
19         int ans = 0;
20         for (int i = 0; i < grid.size(); ++i) {
21             for (int j = 0; j < grid[i].size(); ++j) {
22                 if (grid[i][j] == true) {
23                     help(grid, i, j);
24                     ++ans;
25                 }
26             }
27         }
28         return ans;
29     }
30 };

C++

BFS

 1 class Solution {
2 public:
3     void help(vector<vector<bool>>& a, int x, int y) {
4         queue<pair<int, int> > q;
5         const int dx[] = {-1, 1, 0, 0};
6         const int dy[] = {0, 0, -1, 1};
7         a[x][y] = false;
8         for (q.push(make_pair(x, y)); !q.empty(); q.pop()) {
9             x = q.front().first;
10             y = q.front().second;
11             for (int i = 0; i < 4; ++i) {
12                 int nx = x + dx[i];
13                 int ny = y + dy[i];
14                 if ((nx >= 0) && (nx < a.size()) && (ny >= 0) &&(ny < a[nx].size()) && (a[nx][ny] == true)) {
15                     a[nx][ny] = false;
16                     q.push(make_pair(nx, ny));
17                 }
18             }
19         }
20     }
21     /**
22      * @param grid a boolean 2D matrix
23      * @return an integer
24      */
25     int numIslands(vector<vector<bool>>& grid) {
26         // Write your code here
27         int ans = 0;
28         for (int i = 0; i < grid.size(); ++i) {
29             for (int j = 0; j < grid[i].size(); ++j) {
30                 if (grid[i][j] == true) {
31                     help(grid, i, j);
32                     ++ans;
33                 }
34             }
35         }
36         return ans;
37     }
38 };

|

[leetcode/lintcode 题解] 阿里算法面试真题：丑数 II · Ugly Number II
[leetcode/lintcode 题解] 阿里算法面试真题：丑数 II · Ugly Number II
291 0
|

LeetCode 200：岛屿数量 Number of Islands

803 0
|
Java 数据安全/隐私保护
[LintCode] Number of Islands（岛屿个数）

1235 0
|

|
7月前
|

Leetcode 313. Super Ugly Number

72 1
|
14天前
|

LeetCode 题目 65：有效数字（Valid Number）【python】
LeetCode 题目 65：有效数字（Valid Number）【python】
22 5
|
1月前
|

【LeetCode力扣】单调栈解决Next Greater Number（下一个更大值）问题
【LeetCode力扣】单调栈解决Next Greater Number（下一个更大值）问题
15 0
|
7月前
|

Leetcode Single Number II （面试题推荐）

25 0