LeetCode HOT 100 —— 200 .島嶼問題

題目

給你一個由 ‘1’（陸地）和 ‘0’（水）組成的的二維網格，請你計算網格中島嶼的數量。

島嶼總是被水包圍，并且每座島嶼隻能由水準方向和/或豎直方向上相鄰的陸地連接配接形成。

此外，你可以假設該網格的四條邊均被水包圍。

思路

島嶼類問題通用解法（DFS周遊架構）：

島嶼問題是網格結構DFS的典型代表，可以先了解二叉樹上的DFS周遊方法，然後類比寫出網格結構的DFS周遊

二叉樹DFS周遊：

void traverse(TreeNode root) {
    // 判斷 base case
    if (root == null) {
        return;
    }
    // 通路兩個相鄰結點：左子結點、右子結點
    traverse(root.left);
    traverse(root.right);
}

           

網格 DFS 周遊：

void dfs(int[][] grid, int r, int c) {
    // 判斷 base case
    // 如果坐标 (r, c) 超出了網格範圍，直接傳回
    if (!inArea(grid, r, c)) {
        return;
    }
    // 通路上、下、左、右四個相鄰結點
    dfs(grid, r - 1, c);
    dfs(grid, r + 1, c);
    dfs(grid, r, c - 1);
    dfs(grid, r, c + 1);
}

// 判斷坐标 (r, c) 是否在網格中
boolean inArea(int[][] grid, int r, int c) {
    return 0 <= r && r < grid.length 
        	&& 0 <= c && c < grid[0].length;
}

           

然後需要考慮避免重複周遊，因為網格結構的 DFS 與二叉樹的 DFS 最大的不同之處在于，周遊中可能遇到周遊過的結點

這裡對周遊過的格子指派為2，格子一共三個取值

• 0 —— 海洋格子
• 1 —— 陸地格子（未周遊過）
• 2 —— 陸地格子（已周遊過）

是以可以在模闆中加入避免重複周遊的語句：

void dfs(int[][] grid, int r, int c) {
    // 判斷 base case
    if (!inArea(grid, r, c)) {
        return;
    }
    // 如果這個格子不是島嶼，直接傳回
    if (grid[r][c] != 1) {
        return;
    }
    grid[r][c] = 2; // 将格子标記為「已周遊過」
    
    // 通路上、下、左、右四個相鄰結點
    dfs(grid, r - 1, c);
    dfs(grid, r + 1, c);
    dfs(grid, r, c - 1);
    dfs(grid, r, c + 1);
}

// 判斷坐标 (r, c) 是否在網格中
boolean inArea(int[][] grid, int r, int c) {
    return 0 <= r && r < grid.length 
        	&& 0 <= c && c < grid[0].length;
}
           

這就是島嶼問題、乃至各種網格問題的通用 DFS 周遊方法，然後在此基礎上修改即可。

本題java代碼如下：

class Solution{
	public int numIslands(char[][] grid){
		//定義一個表示島嶼數量的變量
		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'){
					//深度遞歸，周遊所有的陸地
					dfs(grid, i, j);
					//用來統計有多少島嶼，島嶼是由多個陸地組成的，概念不一樣
					count++;
				}
			}
		}
		//傳回島嶼的數量
		return count;
	}
		
	public void dfs(char[][] grid, int i, int j){
		//防止 i 和 j 越界，也就是防止超出島嶼（上下左右）的範圍,周遊到海洋的時候也退出循環
		if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0'){
			return;
		}
		//将周遊過的陸地改為海洋，防止重複周遊
		grid[i][j] = '0';
		//上
		dfs(grid, i + 1, j);
		//下
		dfs(grid, i - 1, j);
		//右
		dfs(grid, i, j + 1);
		//左
		dfs(grid, i, j - 1);
	}
}