POJ 1548 Robots DFS 解法 (貪心逐行清除)

問題重述

同 ID 4644，但此處提供 DFS 視角的解法：機器人只能向右/下移動，求最少路徑覆蓋所有點。DFS 策略：從最左上角的未覆蓋點出發，沿該行向右清除所有可達點，再移至下一行繼續，每啟動一次 DFS 即為一條新路徑。

算法邏輯

1. 讀入所有點，記錄最大行 R、最大列 C。
2. 建立二維標記數組 line[r][c]。
3. 掃描所有網格，若發現未訪問點，啟動 DFS：

void dfs(int x, int y) {
    int pos = y;
    for (int j = y; j <= C; ++j)
        if (line[x][j]) { line[x][j] = 0; pos = j; }
    if (x == R) return;
    dfs(x+1, pos);
}

每次外層啟動 DFS 計數器 +1，最終計數即為最少路徑數。

正確性說明

此貪心策略等價於將問題轉化為偏序集的最小鏈分解，由 Dilworth 定理知最小鏈分解數 = 最大反鏈大小，亦即最大匹配數的補集。DFS 實際構造了鏈分解。

完整代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAX = 35;
int line[MAX][MAX], R, C, ans;

void dfs(int x, int y) {
    int pos = y;
    for (int j = y; j <= C; ++j)
        if (line[x][j]) { line[x][j] = 0; pos = j; }
    if (x == R) return;
    dfs(x+1, pos);
}

int main() {
    int a, b;
    while (cin >> a >> b, a != -1 || b != -1) {
        memset(line, 0, sizeof(line));
        if (!a && !b) { cout << 0 << '\n'; continue; }
        R = C = 0;
        while (a && b) {
            R = max(R, a); C = max(C, b);
            line[a][b] = 1;
            cin >> a >> b;
        }
        ans = 0;
        for (int i = 1; i <= R; ++i)
            for (int j = 1; j <= C; ++j)
                if (line[i][j]) { dfs(i, j); ++ans; }
        cout << ans << '\n';
    }
    return 0;
}

複雜度

每個點最多被訪問一次，O(R·C) ≤ 900，極快。