ZOJ 3861 Valid Pattern Lock：安卓圖案鎖合法性判定 (DFS)

問題描述

3×3 點陣（編號 1..9），給定 n 個「活躍點」（3 ≤ n ≤ 9）。合法圖案需滿足：

1. 序列由活躍點組成，每個點恰好出現一次。
2. 對任意相鄰點 A, B，若連線段經過其他點 C，則 C 必須已在序列中（出現在 A, B 之前）。

輸出所有合法序列（字典序）。

解題思路：DFS + 幾何預判

1. 預計算「中間點」：對任意兩點 u, v，若連線經過另一點 mid[u][v]（如 1→3 經過 2，1→9 經過 5），記錄之。無中間點則為 0。
2. DFS 狀態：(當前點, 已訪問 mask, 當前序列)。
3. 轉移合法性：從 u 到 v 合法當且僅當：
   • v 是活躍點且未訪問。
   • 若 mid[u][v] != 0，則 mid[u][v] 已訪問。
4. 字典序輸出：DFS 時按點編號 1..9 遞增嘗試，自然生成字典序。收集所有長度為 n 的序列。

關鍵代碼片段 (C++)

#include <bits/stdc++.h>
using namespace std;

int pos[10][2] = {{0,0},
    {1,1},{1,2},{1,3},
    {2,1},{2,2},{2,3},
    {3,1},{3,2},{3,3}};
int mid[10][10];  // mid[u][v] = 經過的中間點，0 表示無

void init_mid() {
    memset(mid, 0, sizeof(mid));
    for (int i = 1; i <= 9; ++i)
        for (int j = 1; j <= 9; ++j) if (i != j) {
            int x1 = pos[i][0], y1 = pos[i][1];
            int x2 = pos[j][0], y2 = pos[j][1];
            // 判斷中點是否為整數網格點且在 1..9 內
            if ((x1 + x2) % 2 == 0 && (y1 + y2) % 2 == 0) {
                int mx = (x1 + x2) / 2, my = (y1 + y2) / 2;
                for (int k = 1; k <= 9; ++k)
                    if (pos[k][0] == mx && pos[k][1] == my) {
                        mid[i][j] = k; break;
                    }
            }
        }
}

bool active[10], vis[10];
int n;
vector<vector<int>> ans;
vector<int> path;

void dfs(int u) {
    if ((int)path.size() == n) {
        ans.push_back(path);
        return;
    }
    for (int v = 1; v <= 9; ++v) {
        if (!active[v] || vis[v]) continue;
        int m = mid[u][v];
        if (m && !vis[m]) continue;  // 中間點未訪問
        vis[v] = true;
        path.push_back(v);
        dfs(v);
        path.pop_back();
        vis[v] = false;
    }
}

int main() {
    init_mid();
    int T; cin >> T;
    while (T--) {
        cin >> n;
        fill(active, active+10, false);
        fill(vis, vis+10, false);
        for (int i = 0, x; i < n; ++i) { cin >> x; active[x] = true; }
        ans.clear();
        for (int s = 1; s <= 9; ++s) if (active[s]) {
            vis[s] = true;
            path.push_back(s);
            dfs(s);
            path.pop_back();
            vis[s] = false;
        }
        cout << ans.size() << '\n';
        for (auto &seq : ans) {
            for (int i = 0; i < n; ++i) {
                if (i) cout << ' ';
                cout << seq[i];
            }
            cout << '\n';
        }
    }
    return 0;
}

複雜度分析

• 狀態數 ≤ 9! = 362,880，實際受活躍點限制更少。
• 每狀態轉移 ≤ 9，總操作 ~10^6，極快。
• 字典序輸出天然滿足要求。

總結

ZOJ 3861 將圖案鎖規則建模為圖上的受限 Hamiltonian 路徑問題。關鍵在於預計算「跳過點」關係，DFS 時檢查中間點是否已訪問。代碼結構清晰，利用 mask 或 vis[] 狀態壓縮，按編號遞增搜索自動保證字典序輸出。