【LeetCode】Number of Islands 解题报告
发布时间：2020-12-13 20:07:55 所属栏目：PHP教程 来源：网络整理
导读：【题目】 Given a 2d grid map of '1' s (land) and '0' s (water),count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid a
|
【题目】
Given a 2d grid map of Example 1: 11110
11010 11000 00000 Answer: 1 Example 2: 11000
11000 00100 00011 Answer: 3 【解析】题意：1个只包括字符0和1的2维数组，找出里面不相邻的只包括1的块的个数。 思路：DFS、BFS。只要遍历1遍，碰到1个1，就把它周围所有相连的1都标记为非1，这样全部遍历进程中碰到的1的个数就是所求解。 【Java代码：DFS、递归】 public class Solution {
private int m,n;
public int numIslands(char[][] grid) {
m = grid.length;
if (m == 0) return 0;
n = grid[0].length;
if (n == 0) return 0;
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] != '1') continue;
ans++;
dfs(grid,i,j);
}
}
return ans;
}
public void dfs(char[][] grid,int i,int j) {
if (i < 0 || i >= m || j < 0 || j >= n) return;
if (grid[i][j] == '1') {
grid[i][j] = '2';
dfs(grid,i - 1,j);
dfs(grid,i + 1,j - 1);
dfs(grid,j + 1);
}
}
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |