HDU 1198 Farm Irrigation：管道連通塊計數與 DFS 洪水填充

題目大意

農田為 M×N 格網，每格有一種管道 (A~K 11 種)。管道有固定開口方向 (上下左右)。
水源放置於格中心，水沿管道流動可灌溉經過的格子。
求最少需要幾個水源才能灌溉整個農田 (即連通塊數量)。

管道類型定義

11 種管道開口配置 (上右下左)：

// 索引 0=A, 1=B, ..., 10=K
// up, right, down, left
int up[11]    = {1,1,0,0,1,0,1,1,0,1,1};
int right[11] = {0,1,0,1,0,1,1,0,1,1,1};
int down[11]  = {0,0,1,1,1,0,0,1,1,1,1};
int left[11]  = {1,0,1,0,0,1,1,1,1,0,1};

例如 A(0)：上、左開口；K(10)：四面皆通。

連通判斷邏輯

兩相鄰格子連通需雙向開口：

• 右鄰居：當前 right 且鄰居 left
• 左鄰居：當前 left 且鄰居 right
• 下鄰居：當前 down 且鄰居 up
• 上鄰居：當前 up 且鄰居 down

DFS 連通塊計數

#include 
using namespace std;

const int MAX = 55;
char grid[MAX][MAX];
bool vis[MAX][MAX];
int M, N;

int up[11] = {1,1,0,0,1,0,1,1,0,1,1};
int rt[11] = {0,1,0,1,0,1,1,0,1,1,1};
int dn[11] = {0,0,1,1,1,0,0,1,1,1,1};
int lt[11] = {1,0,1,0,0,1,1,1,1,0,1};
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

void dfs(int x, int y) {
    if (vis[x][y]) return;
    vis[x][y] = true;
    int cur = grid[x][y] - 'A';

    for (int dir = 0; dir < 4; ++dir) {
        int nx = x + dx[dir], ny = y + dy[dir];
        if (nx < 0 || nx >= M || ny < 0 || ny >= N) continue;
        int nxt = grid[nx][ny] - 'A';

        bool connected = false;
        if (dir == 0) connected = rt[cur] && lt[nxt];      // 右
        else if (dir == 1) connected = lt[cur] && rt[nxt]; // 左
        else if (dir == 2) connected = dn[cur] && up[nxt]; // 下
        else connected = up[cur] && dn[nxt];               // 上

        if (connected) dfs(nx, ny);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    while (cin >> M >> N, M > 0 && N > 0) {
        for (int i = 0; i < M; ++i) cin >> grid[i];
        memset(vis, 0, sizeof(vis));

        int ans = 0;
        for (int i = 0; i < M; ++i)
            for (int j = 0; j < N; ++j)
                if (!vis[i][j]) {
                    ++ans;
                    dfs(i, j);
                }
        cout << ans << "\n";
    }
    return 0;
}

複雜度分析

• 時間：O(M×N)，每格最多訪問一次
• 空間：O(M×N) 訪問標記陣列
• M,N ≤ 50，極輕量

測試樣例

輸入:
2 2
DK
HF
3 3
ADC
FJK
IHE
-1 -1

輸出:
2
3

樣例 2 解析：
ADC
FJK
IHE
形成 3 個獨立連通區域 (紅點標示水源位置)。

擴展思考

• 若需輸出具體水源位置：DFS 時記錄每個連通塊任一格子座標
• 並查集 (Union-Find) 亦可解決，適合動態添加管道場景
• 管道類型擴展只需修改開口查表陣列