HDU 1312 Red and Black：DFS 連通區域計數

HDU 1312 Red and Black - 深度優先搜索解題

題意：給定 R 行 C 列的網格，'.' 表示黑色方塊，'@' 表示起始位置，'#' 表示紅色障礙。從 '@' 出發，只能上下左右移動到 '.' 格子。求可到達的黑色方塊總數（含起點）。多測試用例，R,C ≤ 20。

DFS 遞歸實現

利用遞歸搜索，訪問過的格子標記為 '*'（或任意非 '.' 字符），避免重複訪問，無需回溯恢復現場。

代碼（C++）

#include <cstdio>
#include <vector>
#include <string>
using namespace std;

int R, C, cnt;
vector<string> grid;

bool inside(int r, int c) {
    return r >= 0 && c >= 0 && r < R && c < C && grid[r][c] == '.';
}

void dfs(int r, int c) {
    ++cnt;
    grid[r][c] = '*';
    if (inside(r-1, c)) dfs(r-1, c);
    if (inside(r+1, c)) dfs(r+1, c);
    if (inside(r, c-1)) dfs(r, c-1);
    if (inside(r, c+1)) dfs(r, c+1);
}

int main() {
    string line;
    while (cin >> C >> R && C) {
        grid.clear();
        for (int i = 0; i < R; ++i) {
            cin >> line;
            grid.push_back(line);
        }
        cnt = 0;
        for (int i = 0; i < R; ++i)
            for (int j = 0; j < C; ++j)
                if (grid[i][j] == '@') {
                    dfs(i, j);
                    goto output;
                }
        output:
        printf("%d\n", cnt);
    }
    return 0;
}

關鍵點

1. 網格輸入：先讀 C (列數) 再讀 R (行數)，注意順序。
2. 標記訪問：直接修改 grid[r][c] 為 '*'，省去額外 visited 數組。
3. 遞歸深度最大 400，棧安全。
4. 找到 '@' 後用 goto 跳出雙層循環（或用標誌變量）。

複雜度

時間 O(R·C)，空間 O(R·C)（存網格）+ O(R·C) 遞歸棧。