【POJ 3076】 Sudoku

【题目链接】

http://poj.org/problem?id=3076

【算法】

将数独问题转化为精确覆盖问题，用Dancing Links求解

【代码】

#include <algorithm>

#include <bitset>

#include <cctype>

#include <cerrno>

#include <clocale>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <deque>

#include <exception>

#include <fstream>

#include <functional>

#include <limits>

#include <list>

#include <map>

#include <iomanip>

#include <ios>

#include <iosfwd>

#include <iostream>

#include <istream>

#include <ostream>

#include <queue>

#include <set>

#include <sstream>

#include <stdexcept>

#include <streambuf>

#include <string>

#include <utility>

#include <vector>

#include <cwchar>

#include <cwctype>

#include <stack>

#include <limits.h>

using namespace std;

#define MAXS 100000

struct info

{

        int pos,val;

} a[MAXS];

int i,j,cnt;

int mat[][];

char s[];

inline int getRow(int pos)

{

        return (pos - ) /  + ;

}

inline int getCol(int pos)

{

        return (pos - ) %  + ;

}

inline int getGrid(int pos)

{

        int x = getRow(pos),y = getCol(pos);

        return (x - ) /  *  + (y - ) /  + ;

}

struct DancingLinks

{

        int n,m,step,size;

        int U[MAXS],D[MAXS],L[MAXS],R[MAXS],Row[MAXS],Col[MAXS];

        int H[MAXS],S[MAXS];

        int ans[MAXS];

        inline void init(int _n,int _m)

        {

                int i;

                n = _n;

                m = _m;

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

                {

                        S[i] = ;

                        U[i] = D[i] = i;

                        L[i] = i - ;

                        R[i] = i + ;

                }

                L[] = m; R[m] = ;

                size = m;

                for (i = ; i <= n; i++) H[i] = -;

        }

        inline void link(int r,int c)

        {

                size++;

                Row[size] = r;

                Col[size] = c;

                S[c]++;

                D[size] = D[c];

                U[D[c]] = size;

                U[size] = c;

                D[c] = size;

                if (H[r] < ) L[size] = R[size] = H[r] = size;

                else

                {

                        R[size] = R[H[r]];

                        L[R[H[r]]] = size;

                        L[size] = H[r];

                        R[H[r]] = size;

                }

        }

        inline void Remove(int c)

        {

                int i,j;

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

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

                for (i = D[c]; i != c; i = D[i])

                {

                        for (j = R[i]; j != i; j = R[j])

                        {

                                D[U[j]] = D[j];

                                U[D[j]] = U[j];

                                S[Col[j]]--;

                        }

                }

        }

        inline void Resume(int c)

        {

                int i,j;

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

                {

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

                        {

                                D[U[j]] = j;

                                U[D[j]] = j;

                                S[Col[j]]++;

                        }

                }

                L[R[c]] = c;

                R[L[c]] = c;

        }

        inline bool solve(int dep)

        {

                int i,j,c;

                if (R[] == )

                {

                        step = dep;

                        return true;

                }

                c = R[];

                for (i = R[]; i != ; i = R[i])

                {

                        if (S[i] < S[c])

                                c = i;

                }

                Remove(c);

                for (i = D[c]; i != c; i = D[i])

                {

                        ans[dep] = Row[i];

                        for (j = R[i]; j != i; j = R[j])

                                Remove(Col[j]);

                        if (solve(dep+)) return true;

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

                                Resume(Col[j]);

                }

                Resume(c);

                return false;

        }

} DLX;

int main()

{

        while (scanf("%s",s+) != EOF)

        {

                cnt = ;

                memset(mat,,sizeof(mat));

                for (i = ; i < ; i++) scanf("%s",s+i*+);

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

                {

                        if (s[i] != '-')

                        {

                                mat[][i] = ;

                                mat[][+(getRow(i)-)*+s[i]-'A'+] = ;

                                mat[][+(getCol(i)-)*+s[i]-'A'+] = ;

                                mat[][+(getGrid(i)-)*+s[i]-'A'+] = ;

                        } else

                        {

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

                                {

                                        cnt++;

                                        mat[cnt][i] = ;

                                        mat[cnt][+(getRow(i)-)*+j] = ;

                                        mat[cnt][+(getCol(i)-)*+j] = ;

                                        mat[cnt][+(getGrid(i)-)*+j] = ;

                                        a[cnt] = (info){i,j};

                                }

                        }

                }

                DLX.init(cnt,);

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

                {

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

                        {

                                if (mat[i][j])

                                        DLX.link(i,j);

                        }

                }

                DLX.solve();

                for (i = ; i < DLX.step; i++) s[a[DLX.ans[i]].pos] = 'A' + a[DLX.ans[i]].val - ;

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

                {

                        printf("%c",s[i]);

                        if (i %  == ) printf("\n");

                }

                printf("\n");

        }

        return ;

}