200. 島嶼問題

難度：中等
力扣地址：https://leetcode.cn/studyplan/top-100-liked/

問題描述

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

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

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

示例 1：

輸入：grid = [
[“1”,“1”,“1”,“1”,“0”],
[“1”,“1”,“0”,“1”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“0”,“0”,“0”]
]
輸出：1

示例 2：

輸入：grid = [
[“1”,“1”,“0”,“0”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“1”,“0”,“0”],
[“0”,“0”,“0”,“1”,“1”]
]
輸出：3

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] 的值為 '0' 或 '1'

問題分析

有沒有小伙伴跟我一樣，這類題目一看就想嘗試一下深度優先遍歷 DFS ？

DFS 寫起來比較簡單，也比較容易理解，所以真心推薦合適場景下考慮 DFS。

如下圖所示，白色筷子表示 “水”，也就是遍歷時的邊界。

所以接下的問題就非常簡單，我們從 (0, 0) 這個坐標出發，如果是陸地就 travel，也就是 DFS 遍歷，如果是水，就修改方向，如果沒有地方去了，就切換到下一個陸地。

（為了更好理解，我們可以考慮：把經過的陸地，全部都換成水，避免下次還來這個地方）

解題代碼

對應的 C++ 代碼如下：

class Solution {
public:void travel(vector<vector<char>>& grid, int x, int y) {// 遇到邊界或沒有可訪問的點if (x >= grid.size() || x < 0 || y >= grid[0].size() || y < 0 || grid[x][y] == '0') {return;}// 標記一下已經訪問grid[x][y] = '0';// 四個方向 traveltravel(grid, x + 1, y);travel(grid, x - 1, y);travel(grid, x, y + 1);travel(grid, x, y - 1);}int numIslands(vector<vector<char>>& grid) {// 記錄結果int result = 0;// 根據 (i, j) 開始嘗試 travelfor (int i = 0; i < grid.size(); i++) {for (int j = 0; j < grid[0].size(); j++) {// 如果遇到的這個點是陸地if (grid[i][j] == '1') {// 開始traveltravel(grid, i, j);// travel 結束后 + 1，表示那一片陸地已經訪問過了result += 1;}}}return result;}
};

• 時間復雜度：O(MN)
• 空間復雜度：O(MN）

對應的 java 代碼如下：

class Solution {// 定義 travel 方法public void travel(char[][] grid, int x, int y) {// 遇到邊界或沒有可訪問的點if (x >= grid.length || x < 0 || y >= grid[0].length || y < 0 || grid[x][y] == '0') {return;}// 標記已經訪問過的點grid[x][y] = '0';// 四個方向進行遞歸調用travel(grid, x + 1, y);travel(grid, x - 1, y);travel(grid, x, y + 1);travel(grid, x, y - 1);}// 定義 numIslands 方法public int numIslands(char[][] grid) {// 記錄結果int result = 0;// 遍歷整個網格for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[0].length; j++) {// 如果遇到陸地if (grid[i][j] == '1') {// 開始進行遞歸訪問travel(grid, i, j);// 訪問結束后計數加一result++;}}}// 返回結果return result;}
}

對應的python代碼為

class Solution:def travel(self, grid, x, y):# 遇到邊界或沒有可訪問的點if x >= len(grid) or x < 0 or y >= len(grid[0]) or y < 0 or grid[x][y] == '0':return# 標記已經訪問過的點grid[x][y] = '0'# 四個方向進行遞歸調用self.travel(grid, x + 1, y)self.travel(grid, x - 1, y)self.travel(grid, x, y + 1)self.travel(grid, x, y - 1)def numIslands(self, grid):# 記錄結果result = 0# 遍歷整個網格for i in range(len(grid)):for j in range(len(grid[0])):# 如果遇到陸地if grid[i][j] == '1':# 開始進行遞歸訪問self.travel(grid, i, j)# 訪問結束后計數加一result += 1# 返回結果return result

總結

作為 DFS 的一個比較簡單的例子，限制條件也比較少，只需要考慮邊界問題即可。先應該學習一下 DFS 的基本邏輯，然后能夠寫 DFS 的代碼，在此基礎上稍微改改就可以刷這道題。

我更加想稱這個操作為防水游戲，就是把每塊島嶼都用海水淹沒，看看需要操作多少次。

多謝小伙伴們的點贊支持 ~

Smileyan
2024.06.30 23:52