題目與適用情境
給定一個 m × n 二維網格，元素只可能是字元 "1"（陸地）或 "0"（水域）。兩個陸地格只有在水平或垂直相鄰時才連通；一座島嶼是最大的連通陸地集合。回傳島嶼數量。
限制為 1 <= m, n <= 300。實作仍會防禦空陣列，避免把呼叫端限制變成執行期錯誤。預設允許修改輸入網格；若呼叫端要求保留輸入，就改用同尺寸的 visited 矩陣。
這是通用演算法題，適合軟體工程職位的程式設計面試。它考察把矩陣轉成隱式圖、走訪連通分量，以及讓程式與複雜度分析一致。
面試官考察重點
強回答會先把每個陸地格視為頂點，把四方向相鄰視為邊。接著得到關鍵結論：掃描時每遇到一個尚未造訪的陸地格，就發現一個新的連通分量；從該格出發走訪並標記整座島嶼，之後不會重複計數。
實作細節同樣重要。鄰居應在入堆疊時標記，不能等到出堆疊才標記，否則同一格可能被多個鄰居重複推入。迭代 DFS 可避免一整塊陸地造成遞迴呼叫堆疊過深。強回答也會準確說明：原地標記省掉 visited 矩陣，但顯式堆疊最壞仍需 O(mn) 空間。
普通回答常只說「用 DFS」，卻沒有定義連通規則、修改輸入的副作用、正確性不變量或對抗測試。
回答前需要釐清的問題
- 連通是否包含對角線？ 本題只算四方向；若包含八方向，只需擴充方向陣列，答案可能改變。
- 能否修改輸入？ 可以時把造訪過的
"1"改成"0"；不可以時使用visited，時間不變但增加 O(mn) 儲存空間。 - 網格是否規則且非空？ 題目保證矩形且非空；正式函式仍可對空輸入回傳 0。若允許鋸齒陣列，邊界判斷必須依目前列長處理。
- 只求靜態總數，還是持續加入陸地後查詢？ 靜態網格適合 DFS 或 BFS；動態加點更適合不相交集合。
- 資料規模與語言堆疊限制為何？ 300×300 全為陸地時可能形成 90,000 層遞迴路徑，因此此處選擇顯式堆疊。
30 秒回答框架
「我把陸地格看成隱式圖的頂點，四方向相鄰就是邊。逐列掃描網格；每次遇到 1，它一定屬於尚未處理的新連通分量，所以島嶼數加一。接著用顯式堆疊做 DFS，把可到達的陸地在入堆疊時改成 0。這樣每格最多入堆疊一次，不會重複計數，也避開深度遞迴。時間是 O(mn)，顯式堆疊最壞 O(mn)。若輸入不可修改，我會用 visited 矩陣保存造訪狀態。」
分步深入解析
第一步：從暴力重複搜尋找出瓶頸
如果從每個陸地格都獨立搜尋其連通區域，同一座島會被反覆走訪。瓶頸不在尋找鄰居，而在沒有跨搜尋保存「已屬於某個已計數分量」的狀態。
全域掃描搭配永久造訪標記可消除重複：只有掃描遇到尚未標記的陸地時才啟動一次搜尋。
第二步：建立計數不變量
掃描到位置 (r, c) 時，之前啟動過的每次 DFS 恰好標記了一整座島。若目前格仍為 "1"，它不可能屬於這些島，因此必定是新島的起點，計數加一。
從該點出發的 DFS 只沿四方向陸地移動，所以不會跨過水域連接兩座島；同時會造訪所有可到達陸地，因此這座島之後不會再次觸發計數。這同時證明「不漏算」與「不重算」。
第三步：在入堆疊時標記
假設一個未標記格同時鄰接兩個已在堆疊中的格。若等到出堆疊才標記，兩個格都可能把它推入。結果通常仍正確，但堆疊出現重複工作，複雜度推導也變得不精確。
發現鄰居時立刻把它改為 "0"，再推入堆疊。此後任何方向再次看到它都不會重複加入，保證每個陸地格最多入堆疊一次。
第四步：實作迭代 DFS
function numIslands(grid) {
if (grid.length === 0 || grid[0].length === 0) return 0;
const rows = grid.length;
const cols = grid[0].length;
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
let islands = 0;
for (let row = 0; row < rows; row += 1) {
for (let col = 0; col < cols; col += 1) {
if (grid[row][col] !== "1") continue;
islands += 1;
grid[row][col] = "0";
const stack = [[row, col]];
while (stack.length > 0) {
const [currentRow, currentCol] = stack.pop();
for (const [rowOffset, colOffset] of directions) {
const nextRow = currentRow + rowOffset;
const nextCol = currentCol + colOffset;
if (
nextRow >= 0 && nextRow < rows &&
nextCol >= 0 && nextCol < cols &&
grid[nextRow][nextCol] === "1"
) {
grid[nextRow][nextCol] = "0";
stack.push([nextRow, nextCol]);
}
}
}
}
}
return islands;
}掃描檢查 mn 個格；每個陸地格最多入堆疊一次，並檢查四個鄰居，所以時間為 O(mn)。顯式堆疊在全陸地網格上最壞保存 O(mn) 個座標。輸入會被原地修改；若複製網格，複製本身也需要 O(mn) 時間與空間。
第五步：用邊界與對抗案例驗證
至少檢查：空陣列回傳 0；單一水格回傳 0；單一陸地格回傳 1；全水回傳 0；全陸地回傳 1；只有對角線相鄰的兩個陸地回傳 2；題目範例中的三個分離區域回傳 3；300×300 全陸地不會觸發遞迴溢位。
再檢查輸入副作用。若測試後還要重用原網格，應在呼叫前複製，或改用 visited。這項選擇必須寫進介面說明，不能藏在實作裡。
第六步：比較替代方案
BFS 與迭代 DFS 的時間和最壞空間相同。需要按距離分層處理時選 BFS；此處只需走完整個連通分量，兩者都合適。遞迴 DFS 較短，只有在網格夠小或語言明確支援所需深度時才更簡單。不相交集合適合陸地持續加入、每一步都要回傳島嶼數的版本；對一次靜態計數會增加索引與集合維護成本。
高品質示範回答
「這道題等價於統計隱式無向圖的連通分量。每個 1 是頂點，上下左右的 1 之間有邊。我會掃描整個網格：如果目前位置仍是 1，先前的搜尋就沒有到達它，因此發現一座新島，計數加一；接著從它開始迭代 DFS，把整座島改成 0。
我會在鄰居入堆疊時就標記，避免它被多個相鄰格重複推入。選擇顯式堆疊是因為 300×300 全陸地可能形成很深的遞迴路徑。每格最多處理一次，每次只看四個方向，所以時間 O(mn)，堆疊最壞 O(mn)。這個版本會修改輸入；若介面要求保留網格，我會把標記放進 O(mn) 的 visited 矩陣。最後我會用對角線不連通、全水、全陸地和空輸入測試邊界。」
這段回答把建模、計數依據、實作風險、副作用和驗證連成一條推導鏈，不依賴背誦範本。
常見錯誤
- 把對角線也算作連通 → 改變題意並可能少算島嶼 → 方向陣列只保留上下左右。
- 出堆疊時才標記 → 同一格可能被多個鄰居重複推入 → 發現有效鄰居時立即標記再推入。
- 宣稱原地方案空間 O(1) → 忽略顯式堆疊的最壞規模 → 回報輔助空間最壞 O(mn)。
- 遞迴 DFS 不討論深度 → 大片連續陸地可能耗盡語言呼叫堆疊 → 使用迭代走訪或明確規模保證。
- 暗中修改呼叫端資料 → 後續邏輯讀到被清空的網格 → 在介面中說明副作用，必要時使用
visited。 - 每個陸地都重新搜尋 → 同一分量被反覆走訪 → 只從未造訪陸地啟動搜尋。
- 只測一般矩形 → 漏掉空、全水、全陸地與對角線反例 → 用最小、極端和對抗案例覆蓋假設。
追問與應對
追問一：如果不允許修改輸入呢？
建立 m × n 布林矩陣，在入堆疊時把對應位置設為已造訪。計數不變量與時間 O(mn) 不變；額外儲存明確增加到 O(mn)。若允許複製輸入，複製與 visited 的漸進空間相同，只是語意不同。
追問二：如果對角線也算連通呢？
把方向從四個擴充為八個，走訪框架不變。應先用 [[1, 0], [0, 1]] 這類只在對角相鄰的案例確認預期，因為四方向答案為 2，八方向答案為 1。
追問三：如果陸地會逐個加入，並要求每次回傳數量呢？
靜態 DFS 會重複掃描。改用不相交集合：新陸地先讓計數加一，再與每個已存在的相鄰陸地合併；每次成功合併兩個不同集合，計數減一。還要處理重複加入，避免重複加一。
追問四：如果網格非常稀疏且座標範圍巨大呢？
不應配置完整矩陣。用雜湊集合保存實際陸地座標，只走訪這些座標並檢查四鄰居；複雜度以陸地數 k 表示，期望時間 O(k)，造訪集合與堆疊為 O(k)。這改變了輸入表示，只有稀疏座標清單可用時才成立。