HDU 1241 Oil Deposits：油田連通區域計數 (BFS/DFS)

問題描述

給定 m × n 網格（m, n ≤ 100），每個格子為 @（油袋）或 *（無油）。八方向（水平、垂直、對角線）相鄰的油袋屬於同一油田。求油田總數。輸入以 0 0 結束。

解法：洪水填充算法

掃描整個網格，遇到未訪問的 @，計數器加一，啟動 BFS 或 DFS 將其所在連通分量所有 @ 標記為已訪問。八方向偏移量為 (-1,-1) ... (1,1)（排除 (0,0)）。

BFS 實現要點

• 使用隊列存儲待擴展坐標。
• 訪問標記可直接修改網格（將 @ 改為 *）或額外 visited 數組。
• 邊界檢查：0 ≤ nx < m, 0 ≤ ny < n。

複雜度

每個格子最多入隊/出隊一次，時間 O(mn)，空間 O(mn)（隊列最坏情況）。m,n ≤ 100 完全足夠。

參考代碼 (Java BFS)

import java.util.*;

public class OilDeposits {
    static int[] dx = {-1,-1,-1,0,0,1,1,1};
    static int[] dy = {-1,0,1,-1,1,-1,0,1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int m = sc.nextInt();
            int n = sc.nextInt();
            if (m == 0 && n == 0) break;
            char[][] grid = new char[m][n];
            for (int i = 0; i < m; i++) {
                grid[i] = sc.next().toCharArray();
            }
            int count = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == '@') {
                        count++;
                        bfs(grid, i, j, m, n);
                    }
                }
            }
            System.out.println(count);
        }
    }

    static void bfs(char[][] grid, int sx, int sy, int m, int n) {
        Queue q = new LinkedList<>();
        q.offer(new int[]{sx, sy});
        grid[sx][sy] = '*';
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int dir = 0; dir < 8; dir++) {
                int nx = cur[0] + dx[dir];
                int ny = cur[1] + dy[dir];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == '@') {
                    grid[nx][ny] = '*';
                    q.offer(new int[]{nx, ny});
                }
            }
        }
    }
}

DFS 替代方案

遞歸 DFS 代碼更簡潔，但需注意 Java 默認棧深度；100×100=10,000 通常安全。若擔心棧溢出，可用顯式棧模擬或改用 BFS。

總結

• 經典連通分量計數問題，八方向擴展。
• BFS 避免遞歸棧風險，工程上更穩健。
• 原地修改網格標記訪問，節省額外空間。