1.题目描述
2.思路
（1）主函数，存储图结构
（2）主函数，visit数组表示已访问过的元素
（3）辅助函数，用递归（深搜），遍历以已访问过的元素（陆地1）的相邻元素（陆地1）。
补充：深度搜索（递归）
（1）确定递归函数和参数
（2）确定终止条件
（3）单层搜索条件
3.代码实现
public int numIslands(char[][] grid) {
//行数
int row = grid.length;
//列数
int col = grid[0].length;
// visited 用于记录访问状态
boolean[][] visited = new boolean[row][col];//所有数组的元素在创建时都会被自动初始化为默认值。
//岛屿数量初始化
int cnt = 0;
//判空处理,整个图为null，行为0，列为0
if (row == 0 || col == 0 || grid == null) {
return 0;
}
//存储图结构
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) { // 如果当前是陆地且未被访问
if (grid[i][j] == '1' && visited[i][j] == false)
//!visited[i][j] 和visited[i][j]==false 等同
{
cnt++;
dfs(grid, visited, i, j);// 每次DFS表示一个岛屿
}
}
}
return cnt;
}
// 深度优先搜索，将与当前位置相连的陆地都标记为已访问
void dfs(char[][] grid, boolean visited[][], int i, int j) {
int row = grid.length;
int col = grid[0].length;
// 越界或不是陆地或已访问，直接返回,切记因为索引是从0开始的，所以i>=row||j>=col
if (i < 0 || j < 0 || i >= row || j >= col || visited[i][j] == true || grid[i][j] == '0') {
return;
}
// 标记为已访问,把访问过的陆地的相邻陆地标记为已访问过
visited[i][j] = true;
dfs(grid, visited, i + 1, j);
dfs(grid, visited, i - 1, j);
dfs(grid, visited, i, j + 1);
dfs(grid, visited, i, j - 1);
}
public static void main(String[] args) {
H200 test = new H200();
char[][] input = {
{'1', '1', '1', '1', '0'},
{'1', '1', '0', '1', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '0', '0', '0'}
};
int numsIsland = test.numIslands(input);
System.out.print(numsIsland);
}