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 };
复制代码

 


本文转自ZH奶酪博客园博客,原文链接:http://www.cnblogs.com/CheeseZH/p/5012230.html,如需转载请自行联系原作者

相关文章
|
存储 算法
[leetcode/lintcode 题解] 阿里算法面试真题:丑数 II · Ugly Number II
[leetcode/lintcode 题解] 阿里算法面试真题:丑数 II · Ugly Number II
[leetcode/lintcode 题解] 阿里算法面试真题:丑数 II · Ugly Number II
|
算法 Java C语言
LeetCode 200:岛屿数量 Number of Islands
题目: 给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。 Given a 2d grid map of '1's (land) and '0's (water), count the number of islands.
803 0
|
Java 数据安全/隐私保护
[LintCode] Number of Islands(岛屿个数)
描述 给一个01矩阵,求不同的岛屿的个数。 0代表海,1代表岛,如果两个1相邻,那么这两个1属于同一个岛。我们只考虑上下左右为相邻。 样例 在矩阵: [ [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] ] 中有 3 个岛。
1235 0
|
机器学习/深度学习
|
7月前
|
算法
Leetcode 313. Super Ugly Number
题目翻译成中文是『超级丑数』,啥叫丑数?丑数就是素因子只有2,3,5的数,7 14 21不是丑数,因为他们都有7这个素数。 这里的超级丑数只是对丑数的一个扩展,超级丑数的素因子不再仅限于2 3 5,而是由题目给定一个素数数组。与朴素丑数算法相比,只是将素因子变了而已,解法还是和朴素丑数一致的。
72 1
|
14天前
|
存储 SQL 算法
LeetCode 题目 65:有效数字(Valid Number)【python】
LeetCode 题目 65:有效数字(Valid Number)【python】
|
1月前
|
存储 算法
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
15 0
|
7月前
|
存储
Leetcode Single Number II (面试题推荐)
给你一个整数数组,每个元素出现了三次,但只有一个元素出现了一次,让你找出这个数,要求线性的时间复杂度,不使用额外空间。
25 0