php网站后台模板中关村标准化协会

Problem: 200. 岛屿数量

题目描述

思路

该问题可以归纳为一类遍历二维矩阵的题目，此类中的一部分题目可以利用DFS来解决，具体到本题目：

1.我们首先要针对于二维数组上的每一个点，尝试展开DFS
2.我们定义一个和给定矩阵一样大的布尔类型的矩阵visited，用于辅助判断是否开展DFS,若是符合的合法点，则设置为true
3.我们在DFS的具体实现中，以每一个点为基础，从该点的上下左右四个方位开始尝试是否DFS

解题方法

1.定义二维辅助数组visited初始化大小为给定数组grid的大小（若在后续操作中标记某一点为true则表示该位置是已经遍历过的合法位置），定义记录岛屿数量的变量count
2.在主函数（numIslands）中我们遍历二维数组中每一个点，当满足visited[i][j] != true && grid[i][j] == '1’时，则代表此处最少存在一个岛屿count加一，再调用DFS函数
3.DFS函数的具体处理：

3.1 每次先将当前合法位置设置为true（visited中），定义一个二维数组**int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};用于记录当前某一位置的点的四个方位（上下左右）
3.2 for循环（范围1~4），循环中每次执行 int newI = i + directions[k][0];int newJ = j + directions[k][1];**用于记录当前位置的新的位置，并判断当前新位置是否合法，若合法则DFS递归调用（在新的位置的基础上）

复杂度

时间复杂度:

$O(mn)$

空间复杂度:

$O(mn)$

Code

class Solution {private boolean[][] visited;private int row;private int col;/*** Get all the island counts** @param grid Given a two-dimensional array* @return int*/public int numIslands(char[][] grid) {row = grid.length;col = grid[0].length;visited = new boolean[row][col];//The count of islandint count = 0;for (int i = 0; i < row; ++i) {for (int j = 0; j < col; ++j) {if (visited[i][j] != true && grid[i][j] == '1') {count++;dfs(grid, i, j);}}}return count;}/*** Try dfs or not from each point in a two-dimensional array** @param grid Given a two-dimensional array* @param i    Abscissa* @param j    Ordinate*/private void dfs(char[][] grid, int i, int j) {//Record four bearingsint[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};//The current legal location is set to truevisited[i][j] = true;for (int k = 0; k < 4; ++k) {int newI = i + directions[k][0];int newJ = j + directions[k][1];if (newI >= 0 && newI < row && newJ >= 0 && newJ < col&& visited[newI][newJ] == false && grid[newI][newJ] == '1') {dfs(grid, newI, newJ);}}}
}