200. 岛屿数量
程序员文章站
2024-03-26 13:28:53
...
题目:
题解:
典型的dfs模板题,注意一下访问控制条件即可。
代码:
/**
* code200
*/
public class code200 {
public static int numIslands(char[][] grid) {
if(grid.length == 0)
{
return 0;
}
int m = grid.length;
int n = grid[0].length;
boolean visited[][] = new boolean[m][n];
int count = 0;
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
// 如果是岛屿中的一个点,并且没有被访问过,就进行深度优先遍历
if(grid[i][j] == '1' && !visited[i][j])
{
dfs(i, j, m, n, grid, visited);
count++;
}
}
}
return count;
}
// 从坐标为 (i,j) 的点开始进行深度优先遍历
public static void dfs(int i, int j, int m, int n, char grid[][], boolean visited[][])
{
if(i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1' || visited[i][j])
{
return;
}
visited[i][j] = true;
dfs(i + 1, j, m, n, grid, visited);
dfs(i - 1, j, m, n, grid, visited);
dfs(i, j + 1, m, n, grid, visited);
dfs(i, j - 1, m, n, grid, visited);
}
public static void main(String[] args) {
char[][] grid1 = {
{'1', '1', '1', '1', '0'},
{'1', '1', '0', '1', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '0', '0', '0'}};
int res1 = numIslands(grid1);
System.out.println(res1);
char[][] grid2 = {
{'1', '1', '0', '0', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '1', '0', '0'},
{'0', '0', '0', '1', '1'}};
int res2 = numIslands(grid2);
System.out.println(res2);
}
}
参考:
上一篇: 111. 二叉树的最小深度
下一篇: 409. 最长回文串
推荐阅读
-
200. 岛屿数量
-
统计数据库中某个值的数量
-
Mysql常用分组聚合函数(统计行的数量、最大值、最小值、平均值、求和)
-
sql 按照时间来分组, 时间的,年、月、日。统计数量
-
PCL循环分割并提取平面点云——小于阈值数量时停止
-
java基础-参数数量可变的方法 博客分类: Java基础 java可变参数
-
java基础-参数数量可变的方法 博客分类: Java基础 java可变参数
-
oracle 按每隔5分钟统计数量 博客分类: DB2database oracle
-
oracle 按每隔5分钟统计数量 博客分类: DB2database oracle
-
如何使用LIMIT关键字,限制查询结果的数量?