网站建设中iis,网站开发能赚多少钱,四川移动网站建设,网站图片引导页怎么做题目链接
leetcode在线oj题——岛屿数量
题目描述
给你一个由 ‘1’#xff08;陆地#xff09;和 ‘0’#xff08;水#xff09;组成的的二维网格#xff0c;请你计算网格中岛屿的数量。
岛屿总是被水包围#xff0c;并且每座岛屿只能由水平方向和/或竖直方向上相…题目链接
leetcode在线oj题——岛屿数量
题目描述
给你一个由 ‘1’陆地和 ‘0’水组成的的二维网格请你计算网格中岛屿的数量。
岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外你可以假设该网格的四条边均被水包围。
题目示例
输入grid [ [“1”,“1”,“1”,“1”,“0”], [“1”,“1”,“0”,“1”,“0”], [“1”,“1”,“0”,“0”,“0”], [“0”,“0”,“0”,“0”,“0”] ] 输出1
输入grid [ [“1”,“1”,“0”,“0”,“0”], [“1”,“1”,“0”,“0”,“0”], [“0”,“0”,“1”,“0”,“0”], [“0”,“0”,“0”,“1”,“1”] ] 输出3
题目提示
m grid.lengthn grid[i].length1 m, n 300grid[i][j] 的值为 ‘0’ 或 ‘1’
解题思路
定义一个isUsed数组记录遍历过的位置
使用深度优先搜索将与一个位置连接的所有“1”都记录为以遍历最后统计总数即可
定义一个DFS方法参数分别是grid数组行数列数当前所在行当前所在列isUsed数组
将当前的位置的isUsed数组位置更新为已遍历并且分别遍历其上下左右四个位置如果没有越界并且还是“1”那么继续递归其他位置
代码
class Solution {int[][] nextPosition {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};void DFS(char[][] grid, int row, int col, int curX, int curY, boolean[][] isUsed){isUsed[curX][curY] true;//确定下一个位置for (int i 0; i 4; i) {int newX curX nextPosition[i][0];int newY curY nextPosition[i][1];//判断是否越界if(newX row || newX 0 || newY col || newY 0){continue;}if(grid[newX][newY] 1 !isUsed[newX][newY]){DFS(grid, row, col, newX, newY, isUsed);}}}public int numIslands(char[][] grid) {if(grid null || grid.length 0){return 0;}int row grid.length;int col grid[0].length;boolean[][] isUsed new boolean[row][col];int num 0;for (int i 0; i row; i) {for (int j 0; j col; j) {if(grid[i][j] 1 !isUsed[i][j]){num;DFS(grid, row, col, i, j, isUsed);}}}return num;}
}
