admin 管理员组文章数量: 887006
java岛屿
题目：
给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输入:
11110
11010
11000
00000
输出: 1
示例 2:
输入:
11000
11000
00100
00011
输出: 3
解题：
思路一：DFS
直觉
将二维网格看成一个无向图，竖直或水平相邻的 1 之间有边。
算法
线性扫描整个二维网格，如果一个结点包含 1，则以其为根结点启动深度优先搜索。在深度优先搜索过程中，每个访问过的结点被标记为 0。计数启动深度优先搜索的根结点的数量，即为岛屿的数量。
classSolution {void dfs(char[][] grid, int r, intc) {int nr =grid.length;int nc = grid[0].length;if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {return;
}
grid[r][c]= '0';//将原本为1的元素修改为'0'
dfs(grid, r - 1, c); //遍历上下左右四个方向
dfs(grid, r + 1, c);
dfs(grid, r, c- 1);
dfs(grid, r, c+ 1);
}public int numIslands(char[][] grid) {if (grid == null || grid.length == 0) {return 0;
}int nr =grid.length;int nc = grid[0].length;int num_islands = 0;for (int r = 0; r < nr; ++r) {for (int c = 0; c < nc; ++c) {if (grid[r][c] == '1') {++num_islands;
dfs(grid, r, c);//将‘1’周边的‘1’修改为‘0’
}
}
}returnnum_islands;
}
}
思路二：BFS
算法
线性扫描整个二维网格，如果一个结点包含 1，则以其为根结点启动广度优先搜索。将其放入队列中，并将值设为 0 以标记访问过该结点。迭代地搜索队列中的每个结点，直到队列为空。
classSolution {public int numIslands(char[][] grid) {if (grid == null || grid.length == 0) {return 0;
}int nr =grid.length;int nc = grid[0].length;int num_islands = 0;for (int r = 0; r < nr; ++r) {for (int c = 0; c < nc; ++c) {if (grid[r][c] == '1') {++num_islands;
bfs(grid, r, c);
}
}
}returnnum_islands;
}//广度优先搜索
void bfs(char[][] grid, int r, intc) {int nr =grid.length;int nc = grid[0].length;if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {return;
}
grid[r][c]= '0';//将原本为1的元素修改为'0'
Queue bfsQueue = new LinkedList<>();
bfsQueue.add(r* nc +c);while (!bfsQueue.isEmpty()) {int id =bfsQueue.remove();int row = id /nc;int col = id %nc;if (row - 1 >= 0 && grid[row - 1][col] == '1') {
bfsQueue.add((row- 1) * nc +col);
grid[row- 1][col] = '0';
}if (row + 1 < nr && grid[row + 1][col] == '1') {
bfsQueue.add((row+ 1) * nc +col);
grid[row+ 1][col] = '0';
}if (col - 1 >= 0 && grid[row][col - 1] == '1') {
bfsQueue.add(row* nc + col - 1);
grid[row][col- 1] = '0';
}if (col + 1 < nc && grid[row][col + 1] == '1') {
bfsQueue.add(row* nc + col + 1);
grid[row][col+ 1] = '0';
}
}
}
}
链接：/
本文标签： java岛屿
版权声明：本文标题：java岛屿 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732351614h1533233.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论