深度遍历-求“岛屿数量”

本文主要是介绍深度遍历-求“岛屿数量”，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、问题描述

二、解题思路

1.设置一个对应的boolean二维数组 isfind[][] ，用来标记已经遍历过的“岛屿”

2.使用双层循环遍历岛屿（grid）二维数组，当遇到 isfind[i][j]=false 时表示遇到一个新岛屿

3.当遇到新岛屿时进行深度递归遍历，向左、向上、向下、向右尝试“走动”，当新的 i,j位置 满足：

(1) i、j满足二维数组的索引范围

(2)grid[i][j]==1;//当前是岛屿

(3)isfind[i][j]==1;//当前岛屿未访问过

上面蓝色和红色就是两个不同的岛屿，同时红色在向右侧走时发现了满足条件的岛屿（红色星星标注），会合并入第二个岛屿。

三、代码实现

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** 判断岛屿数量* @param grid char字符型二维数组 * @return int整型*/public int solve (char[][] grid) {int rowsize=grid.length;int colsize=grid[0].length;//设置一个对应的boolean二维数组boolean[][] isfinded=new boolean[rowsize][colsize];int islandNum=0;//双层循环遍历grid二维数组，当遇到isfind[i][j]=false时表示遇到一个新岛屿for(int i=0;i<rowsize;i++){for(int j=0;j<colsize;j++){if(grid[i][j]=='1'&&!isfinded[i][j]){islandNum++;allDirectionFind(grid,i,j,isfinded);}}}return islandNum;}public void allDirectionFind(char[][] grid,int row,int col,boolean[][] isfinded){int rowsize=grid.length;int colsize=grid[0].length;if(!isfinded[row][col]){isfinded[row][col]=true;if(row+1<rowsize){//可向下if(grid[row+1][col]=='1'&&!isfinded[row+1][col]){allDirectionFind(grid,row+1,col,isfinded);}}if(row-1>=0){//可向上if(grid[row-1][col]=='1'&&!isfinded[row-1][col]){allDirectionFind(grid,row-1,col,isfinded);}}if(col+1<colsize){//可向右if(grid[row][col+1]=='1'&&!isfinded[row][col+1]){allDirectionFind(grid,row,col+1,isfinded);}}if(col-1>=0){//可向左if(grid[row][col-1]=='1'&&!isfinded[row][col-1]){allDirectionFind(grid,row,col-1,isfinded);}}}}
}