wap手机商城网站源码,贵州微信网站建设,wordpress 随机头像,台州建设局网站建筑工程黑名单给你一个由 1#xff08;陆地#xff09;和 0#xff08;水#xff09;组成的的二维网格#xff0c;请你计算网格中岛屿的数量。
岛屿总是被水包围#xff0c;并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外#xff0c;你可以假设该网格的四条边…给你一个由 1陆地和 0水组成的的二维网格请你计算网格中岛屿的数量。
岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外你可以假设该网格的四条边均被水包围。
示例 1
输入grid [[1,1,1,1,0],[1,1,0,1,0],[1,1,0,0,0],[0,0,0,0,0]
]
输出1示例 2
输入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
方法1DFS(系统栈递归)
这题让求的是岛屿的数量二维数组中值是1的都是岛屿如果多个1是连着的那么他们只能算一个岛屿。
思路
最简单的一种方式就是遍历数组中的每一个值如果是1就说明是岛屿然后把它置为0或者其他的字符都可以只要不是1就行然后再遍历他的上下左右4个位置。如果是1说明这两个岛屿是连着的只能算是一个岛屿我们还要把它置为0然后再以它为中心遍历他的上下左右4个位置……。如果是0就说明不是岛屿就不在往他的上下左右4个位置遍历了。这里就以示例1为例来看一下 public int numIslands(char[][] grid) {//边界条件判断if (grid null || grid.length 0)return 0;//统计岛屿的个数int count 0;//两个for循环遍历每一个格子for (int i 0; i grid.length; i)for (int j 0; j grid[0].length; j) {//只有当前格子是1才开始计算if (grid[i][j] 1) {//如果当前格子是1岛屿的数量加1count;//然后通过dfs把当前格子的上下左右4//个位置为1的都要置为0因为他们是连着//一起的算一个岛屿dfs(grid, i, j);}}//最后返回岛屿的数量return count;
}//这个方法会把当前格子以及他邻近的为1的格子都会置为0
public void dfs(char[][] grid, int i, int j) {//边界条件判断不能越界if (i 0 || i grid.length || j 0 || j grid[0].length || grid[i][j] 0)return;//把当前格子置为0然后再从他的上下左右4个方向继续遍历grid[i][j] 0;dfs(grid, i - 1, j);//上dfs(grid, i 1, j);//下dfs(grid, i, j 1);//左dfs(grid, i, j - 1);//右
}方法2BFS(队列)
DFS就是沿着一条路径一直走下去当遇到终止条件的时候才会返回而BFS就是先把当前位置附近 的访问一遍就像下面这样先访问圈内的然后再把圈放大继续访问就像下面这样 这题使用BFS和DFS都能解决如果遇到位置为1的格子只要能把他们挨着的为1的全部置为0然后挨着的挨着的为1的位置也置为0然后…一直这样循环下去看下代码
public int numIslands(char[][] grid) {//边界条件判断if (grid null || grid.length 0)return 0;//统计岛屿的个数int count 0;//两个for循环遍历每一个格子for (int i 0; i grid.length; i)for (int j 0; j grid[0].length; j) {//只有当前格子是1才开始计算if (grid[i][j] 1) {//如果当前格子是1岛屿的数量加1count;//然后通过bfs把当前格子的上下左右4//个位置为1的都要置为0因为他们是连着//一起的算一个岛屿bfs(grid, i, j);}}return count;
}private void bfs(char[][] grid, int x, int y) {//把当前格子先置为0grid[x][y] 0;int n grid.length;int m grid[0].length;//使用队列存储的是格子坐标转化的值QueueInteger queue new LinkedList();//我们知道平面坐标是两位数字但队列中存储的是一位数字//所以这里是把两位数字转化为一位数字int code x * m y;//坐标转化的值存放到队列中queue.add(code);while (!queue.isEmpty()) {//出队code queue.poll();//在反转成坐标值ijint i code / m;int j code % m;if (i 0 grid[i - 1][j] 1) {//上//如果上边格子为1把它置为0然后加入到队列中//下面同理grid[i - 1][j] 0;queue.add((i - 1) * m j);}if (i n - 1 grid[i 1][j] 1) {//下grid[i 1][j] 0;queue.add((i 1) * m j);}if (j 0 grid[i][j - 1] 1) { //左grid[i][j - 1] 0;queue.add(i * m j - 1);}if (j m - 1 grid[i][j 1] 1) {//右grid[i][j 1] 0;queue.add(i * m j 1);}}
}
