HDU 4069 数独

　　好久没做题了，建图搞了好久…… 然后，判是否有多解的时候会把原来的答案覆盖掉…… 这里没注意，弄了一下午……

代码：

　　

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <string>

#include <queue>

#include <stack>

#include <vector>

#include <map>

#include <set>

#include <functional>

#include <cctype>

#include <time.h>

using namespace std;

const int INF = <<;

const int MAXN = **+;

const int MAXR = **+;

const int MAXNODE = MAXN*MAXR+;

struct DLX {

// 行编号从1开始，列编号为1~n，结点0是表头结点；结点1~n是各列顶部的虚拟结点

    int n, sz; // 列数，结点总数

    int S[MAXN]; //各列结点数

    int row[MAXNODE], col[MAXNODE]; //各结点行列编号

    int L[MAXNODE], R[MAXNODE], U[MAXNODE], D[MAXNODE]; //十字链表

    int ansd, ans[MAXR]; // 解

    void init(int n)  { //n是列数

        this->n = n;

        //虚拟结点

        for (int i = ; i <= n; i++) {

            U[i] = i; D[i] = i; L[i] = i-; R[i] = i+;

        }

        R[n] = ; L[] = n;

        sz = n+;

        memset(S, , sizeof(S));

    }

    void addRow(int r, vector<int> columns) {

        //这一行的第一个结点

        //行没有设头结点，每一行连成一个环形

        int first = sz;

        for (int i = ; i < columns.size(); i++) {

            int c = columns[i];

            L[sz] = sz-; R[sz] = sz+; D[sz] = c; U[sz] = U[c];

            D[U[c]] = sz; U[c] = sz;

            row[sz] = r; col[sz] = c;

            S[c]++; sz++;

        }

        R[sz-] = first; L[first] = sz-;

    }

    //顺着链表A，遍历s外的其他元素

    #define FOR(i, A, s) for (int i = A[s]; i != s; i = A[i])

    void remove(int c) { //删除c列

        L[R[c]] = L[c]; R[L[c]] = R[c];

        for (int i = D[c]; i != c; i = D[i]) // 对于每一个c列不为0的所有行

            for (int j = R[i]; j != i; j = R[j]) { //删除这一整行

                U[D[j]] = U[j]; D[U[j]] = D[j]; S[col[j]]--;

            }

    }

    void restore(int c) { //回连c列

        for (int i = U[c]; i != c; i = U[i])

            for (int j = L[i]; j != i; j = L[j]) {

                U[D[j]] = j; D[U[j]] = j; S[col[j]]++;

            }

        L[R[c]] = c; R[L[c]] = c;

    }

    int flag;

    void dfs(int d) { //d为递归深度

        if (R[] == ) { //找到解

            ansd = d; //记录解的长度

            flag++;

            return ;

        }

        //找S最小的C列

        int c = R[]; //第一个未删除的列

        for (int i = R[]; i != ; i = R[i]) if (S[i]<S[c]) c = i;

        remove(c); //删除第c列

        for (int i = D[c]; i != c; i = D[i]) { //用结点i所在的行覆盖第c列

            if (!flag) ans[d] = row[i];

            for (int j = R[i]; j != i; j = R[j]) remove(col[j]); //删除节结点i所在行覆盖第c列

            dfs(d+);

            if (flag>) return ;

            for (int j = L[i]; j != i; j = L[j]) restore(col[j]); // 恢复

        }

        restore(c); //恢复

    }

    int solve(vector<int> &v) {

        v.clear();

        flag = ;

        dfs();

        for (int i = ; i < ansd; i++) v.push_back(ans[i]);

        return flag;

    }

};

const int dir[][] = { {-, }, {, }, {, }, {, -} };

const int SLOT = ;

const int ROW = ;

const int COL = ;

const int SUB = ;

inline int encode(int a, int b, int c) { return a*+b*+c+; }

inline void decode(int code, int &a, int &b, int &c) {

    code--;

    c = code%; code /= ;

    b = code%; code /= ;

    a = code;

}

DLX solver;

int Matrix[][];

int belong[][];

int cnt;

vector<int> columns;

void test() { int *p = ; (*p) = ; }

void dfs(int r, int c, int num) {

    belong[r][c] = cnt;

    int t = Matrix[r][c]>>;

    int nr, nc;

    for (int i = ; i < ; i++) if (!(t&(<<i))) {

        nr = r+dir[i][]; nc = c+dir[i][];

        if (!(<=nr&&nr<)||!(<=nc&&nc<)||belong[nr][nc]!=-) continue;

        dfs(nr, nc, num+);

    }

}

void solve() {

    solver.init(**);

    for (int r = ; r < ; r++) {

        for (int c = ; c < ; c++) {

            Matrix[r][c] %= ;

            for (int v = ; v <= ; v++) {

                if (Matrix[r][c]!= && Matrix[r][c]!=v) continue;

                columns.clear();

                columns.push_back(encode(SLOT, r, c));

                columns.push_back(encode(ROW, r, v-));

                columns.push_back(encode(COL, c, v-));

                columns.push_back(encode(SUB, belong[r][c], v-));

                solver.addRow(encode(r, c, v-), columns);

            }

        }

    }

    int ans = solver.solve(columns);

    if (ans == ) { puts("Multiple Solutions"); return; }

    if (ans == ) { puts("No solution"); return; }

    for (int i = ; i < columns.size(); i++) {

        int r, c, v;

        decode(columns[i], r, c, v);

        Matrix[r][c] = v+;

    }

    for (int r = ; r < ; r++) {

        for (int c = ; c < ; c++) {

            printf("%d", Matrix[r][c]);

        }

        puts("");

    }

}

int main() {

    #ifdef Phantom01

        freopen("HDU4069.txt", "r", stdin);

//        freopen("HDU4069.out", "w", stdout);

    #endif //Phantom01

    int T;

    scanf("%d", &T);

    for (int C = ; C <= T; C++) {

        printf("Case %d:\n", C);

        for (int i = ; i < ; i++)

            for (int j = ; j < ; j++)

                scanf("%d", &Matrix[i][j]);

        for (int r = ; r < ; r++)

            for (int c = ; c < ; c++)

                belong[r][c] = -;

        cnt = ;

        for (int r = ; r < ; r++) {

            for (int c = ; c < ; c++) if (belong[r][c]==-){

                dfs(r, c, );

                cnt++;

            }

        }

        solve();

    }

    return ;

}