200. 岛屿数量

问题200 岛屿数量 ★★☆☆☆

https://leetcode-cn.com/problems/number-of-islands/

从深度优先遍历的角度来考虑这个题目，思路就比较清晰了，以某一个节点为起始，按照一定顺序去深度优先遍历值为1的节点，并标注访问状态，直到没有能到达的值为1的节点结束，这样就等于把某一个连通的岛屿的所有节点全部访问到并标注了访问状态。上层做二维数组遍历，碰到值为1的节点并且尚未标注访问状态的，说明碰到了新岛屿，那么从这个节点开始做深度优先遍历。

这个题目和问题130很像，DFS的过程是一致的，相比问题130，问题200只需要计数，还更简单些。

	private int[] dx = {-1, 1, 0, 0};
	private int[] dy = {0, 0, -1, 1};

	public int numIslands(char[][] grid) {
		int m = grid.length;
		int n = grid[0].length;

		boolean[][] visited = new boolean[m][n];

		int num = 0;

		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (grid[i][j] == '1'
					&& !visited[i][j]) {
					num++;
					dfs(grid, i, j, visited);
				}
			}
		}

		return num;
	}

	private void dfs(char[][] grid, int i, int j, boolean[][] visited) {
		if (visited[i][j]
			|| grid[i][j] == '0') {
			return;
		}

		visited[i][j] = true;

		for (int k = 0; k < 4; k++) {
			int x = i + dx[k];
			int y = j + dy[k];

			if (isValidIndex(grid, x, y)
				&& grid[x][y] == '1'
				&& !visited[x][y] ) {
				dfs(grid, x, y, visited);
			}
		}
	}

	private boolean isValidIndex(char[][] grid, int i, int j) {
		int m = grid.length;
		int n = grid[0].length;

		if (i < 0 || i >= m) {
			return false;
		}

		if (j < 0 || j >= n) {
			return false;
		}

		return true;
	}

在 LeetCode 查看