📘 題目敘述
給你一個 m x n 的二維二進位網格
grid，它代表一張由 '1'（陸地）與
'0'（水）組成的地圖，請回傳島嶼的數量。
島嶼被水包圍，並且由水平或垂直相鄰的陸地連接形成。你可以假設網格的四個邊緣都被水包圍。
條件限制
m == grid.lengthn == grid[i].length1 <= m, n <= 300-
grid[i][j]是'0'或'1'
🧠 解題思路
這題我用 DFS 做「淹島」的概念。
我一格一格掃描 grid：只要遇到
'1'，代表我發現了一座新的島，所以島的數量
count++。接著我就從這格開始做
DFS，把同一座島上所有連在一起的 '1' 全部改成
'0'，等於把這座島整個消掉，避免之後掃描到同一座島又重複計數。
為了讓 DFS 可以往四個方向走，我用 dx、dy
存上下左右的位移。
所有變數
m：grid的列數n：grid的行數-
dx：四個方向的 x 位移{1, -1, 0, 0} -
dy：四個方向的 y 位移{0, 0, 1, -1} count：目前已找到的島嶼數量-
filled(x, y, grid)：把(x, y)所在島嶼用 DFS 全部標記掉（把'1'變'0'）
🪜 主要流程步驟
1. 先記下 m、n，準備做整張圖的掃描
在 numIslands 一開始先設定：
m = grid.size()n = grid[0].size()
2. 用雙層迴圈掃描每一格
對每個 (i, j)：
-
如果
grid[i][j] == '1'，代表找到一座新島。我就先count++，再呼叫filled(i, j, grid)把整座島清掉。
3. filled 的邊界判斷，避免走出地圖
filled(x, y, grid) 進來後，先檢查：
-
x < 0或x >= m或y < 0或y >= n，直接return。
這樣 DFS 才不會越界。
4. 如果這格是陸地，就把它改成水，並往四個方向擴散
如果 grid[x][y] == '1'：
- 先把它標記成走過：
grid[x][y] = '0' -
然後用
k = 0..3走四個方向，下一格是(x + dx[k], y + dy[k])，對那格繼續呼叫filled(...)
這一步會把「同一座島所有連通的陸地」全部清成 '0'。
5. 掃描結束後，count 就是答案
因為每座島第一次被遇到時會 count++，而且同座島會立刻被
DFS 清掉，所以不會重複計數。
⏱️ 複雜度
-
時間複雜度：
O(m * n)，每個格子最多被 DFS 處理一次（從'1'變'0'）。 -
空間複雜度：
O(m * n)（最壞情況遞迴深度可能到整張圖大小；若改成 iterative DFS/BFS 可避免遞迴爆棧的風險）。
💻 程式碼實作
class Solution {
public:
int m;
int n;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int count = 0;
void filled(int x, int y, vector<vector<char>>& grid) {
if (x < 0 || x >= m || y < 0 || y >= n) {
return;
}
if (grid[x][y] == '1') {
grid[x][y] = '0';
for (int k = 0; k < 4; k++) {
filled(x + dx[k], y + dy[k], grid);
}
}
return;
}
int numIslands(vector<vector<char>>& grid) {
m = grid.size();
n = grid[0].size();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
count++;
filled(i, j, grid);
}
}
}
return count;
}
};