AOJ 0118 財產分配：廣度優先搜索解法詳解

問題描述

本題要求在一個由字符組成的網格中，計算連通區域的數量。網格包含多種字符（如 #、*、@），相同字符且上下左右相鄰的格子視為同一區域。輸入以兩個 0 結束，輸出區域總數。例如給定 10×10 的網格，輸出為 33。

解題思路

採用深度優先搜索（DFS）遍歷網格。定義四個方向向量（上、右、下、左），從未訪問的格子出發，遞歸標記所有相連的相同字符格子為已訪問（如標記為 !），每完成一次 DFS 計數器加一。最終計數器即為區域數。

關鍵代碼實現

#include <iostream>
using namespace std;
#define MAX_W 100
#define MAX_H 100
char room[MAX_W][MAX_H];
int W, H;
const int direc[4][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};

void dfs(const int& row, const int& col, const char c) {
    room[row][col] = '!';
    for (int d = 0; d < 4; ++d) {
        int curRow = row + direc[d][0];
        int curCol = col + direc[d][1];
        if (curRow >= 0 && curRow < H && curCol >= 0 && curCol < W && room[curRow][curCol] == c) {
            dfs(curRow, curCol, c);
        }
    }
}

int main() {
    while (cin >> H >> W, W > 0) {
        int step = 0;
        for (int row = 0; row < H; ++row)
            for (int col = 0; col < W; ++col)
                cin >> room[row][col];
        for (int row = 0; row < H; ++row)
            for (int col = 0; col < W; ++col)
                if (room[row][col] != '!') {
                    dfs(row, col, room[row][col]);
                    ++step;
                }
        cout << step << endl;
    }
    return 0;
}

總結

本題是經典的連通分量計數問題，DFS 實現簡潔高效。注意邊界條件與訪問標記的處理，避免重複計算。