POJ 1979 Red and Black：DFS 洪水填充計算可達黑瓦片數

題目

W×H (≤20) 網格，@ 起點，. 黑瓦可走，# 紅瓦阻隔。四方向移動，求可達黑瓦總數（含起點）。多測試用例，0 0 結束。

解法：遞歸 DFS

1. 讀入網格，記錄起點座標。
2. DFS 四鄰域：邊界檢查、未訪問、為 '.' 則遞歸，計數器累加。
3. 訪問標記：將走過格子改為 '#' 避免重複。

C++ 代碼

#include 
using namespace std;
const int MAX = 20;
char grid[MAX][MAX];
int W, H, cnt;
const int dx[4] = {0,1,0,-1};
const int dy[4] = {-1,0,1,0};

int dfs(int x, int y) {
    grid[x][y] = '#'; // 標記已訪問
    ++cnt;
    for (int d = 0; d < 4; ++d) {
        int nx = x + dx[d], ny = y + dy[d];
        if (nx>=0 && nx=0 && ny> W >> H, W) {
        cnt = 0;
        int sx=0, sy=0;
        for (int i = 0; i < H; ++i)
            for (int j = 0; j < W; ++j) {
                cin >> grid[i][j];
                if (grid[i][j] == '@') { sx = i; sy = j; }
            }
        cout << dfs(sx, sy) << "\n";
    }
    return 0;
}

複雜度

• 時間：O(W×H)，每格最多訪問一次。
• 空間：O(W×H) 遞歸棧（最大 400，安全）。

注意

• 輸入順序：先 W 後 H，但存儲用 [H][W]。
• 起點 @ 也視為黑瓦，DFS 入口直接從 @ 開始，內部邏輯統一判斷 '.'，故先將 @ 位置視為已訪問（計數器在入口遞增）。