POJ 3076 Sudoku

思路：
dfs + 剪枝
首先，如果这个位置只能填一种字母，那就直接填
其次，如果对于每一种字母，如果某一列或者某一行或者某一块只能填它，那就填它
然后，对于某个位置如果不能填字母了，或者某种字母在一行一列或一块中出向了两次以上，说明当前方案不成立
最后贪心地从可选情况少的往下搜
代码:
#pragma GCC optimize(2)

#pragma GCC optimize(3)

#pragma GCC optimize(4)

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

#define fi first

#define se second

#define pi acos(-1.0)

#define LL long long

//#define mp make_pair

#define pb push_back

#define ls rt<<1, l, m

#define rs rt<<1|1, m+1, r

#define ULL unsigned LL

#define pll pair<LL, LL>

#define pii pair<int, int>

#define piii pair<pii, int>

#define mem(a, b) memset(a, b, sizeof(a))

#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);

//head

const int N = ;

int mp[N][N];

int st[N][N];

int sum = ;

char s[N][N+];

void add(int x, int y, int t) {

    mp[x][y] = t;

    sum++;

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

        st[i][y] |= <<t-;

        st[x][i] |= <<t-;

    }

    int xx = (x+)/, yy = (y+)/;

    for (int i = (xx-)* + ; i <= xx*; i++) {

        for (int j = (yy-)* + ; j <= yy*; j++) {

            st[i][j] |= <<t-;

        }

    }

}

void print() {

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

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

            putchar(mp[i][j]-+'A');

        }

        puts("");

    }

    puts("");

}

bool dfs() {

    if(sum == ) {

        print();

        return true;

    }

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

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

            if(!mp[i][j]) {

                int cnt = , t = ;

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

                    if((st[i][j] & (<<k-)) == ) {

                        cnt++;

                        t = k;

                        if(cnt == ) break;

                    }

                }

                if(!cnt) return false;

                if(cnt == ) add(i, j, t);

            }

        }

    }

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

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

            int cnt1 = , cnt2 = , y;

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

                if(mp[i][j] == k) cnt1++;

                if(cnt1 == ) return false;

                if(!mp[i][j] && (st[i][j] & (<<k-)) == ) cnt2++, y = j;

            }

            if(!cnt1 && !cnt2) return false;

            if(!cnt1 && cnt2 == ) add(i, y, k);

        }

    }

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

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

            int cnt1 = , cnt2 = , x;

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

                if(mp[i][j] == k) cnt1++;

                if(cnt1 == ) return false;

                if(!mp[i][j] && (st[i][j] & (<<k-)) == ) cnt2++, x = i;

            }

            if(!cnt1 && !cnt2) return false;

            if(!cnt1 && cnt2 == ) add(x, j, k);

        }

    }

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

        int x = (i+)/, y = i - (x-)*;

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

            int cnt1 = , cnt2 = , xx, yy;

            for (int ii = (x-)*+; ii <= x*; ii++) {

                for (int jj = (y-)*+; jj <= y*; jj++) {

                    if(mp[ii][jj] == k) cnt1++;

                    if(cnt1 == ) return false;

                    if(!mp[ii][jj] && (st[ii][jj] & (<<k-)) == ) cnt2++, xx = ii, yy = jj;

                }

            }

            if(!cnt1 && !cnt2) return false;

            if(!cnt1 && cnt2 == ) add(xx, yy, k);

        }

    }

    if(sum == ) {

        print();

        return true;

    }

    int mn = N, x, y;

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

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

            if(!mp[i][j]) {

                int cnt = ;

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

                    if((st[i][j] & (<<k-)) == ) {

                        cnt++;

                        if(cnt >= mn) break;

                    }

                }

                if(cnt < mn) {

                    mn = cnt;

                    x = i;

                    y = j;

                }

            }

        }

    }

    int tst[N][N], tmp[N][N];

    memcpy(tst, st, sizeof(st));

    memcpy(tmp, mp, sizeof(mp));

    int tsum = sum;

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

        if((st[x][y] & (<<k-)) == ) {

            add(x, y, k);

            bool f = dfs();

            if(!f) {

                memcpy(st, tst, sizeof(tst));

                memcpy(mp, tmp, sizeof(tmp));

                sum = tsum;

            }

            else return true;

        }

    }

    return false;

}

int main() {

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

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

            scanf("%s", s[i]+);

        }

        sum = ;

        mem(mp, );

        mem(st, );

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

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

                if(isalpha(s[i][j])) add(i, j, s[i][j] - 'A' + );

            }

        }

        dfs();

    }

    return ;

}

/*

--A----C-----O-I

-J--A-B-P-CGF-H-

--D--F-I-E----P-

-G-EL-H----M-J--

----E----C--G---

-I--K-GA-B---E-J

D-GP--J-F----A--

-E---C-B--DP--O-

E--F-M--D--L-K-A

-C--------O-I-L-

H-P-C--F-A--B---

---G-OD---J----H

K---J----H-A-P-L

--B--P--E--K--A-

-H--B--K--FI-C--

--F---C--D--H-N-

*/
巴特西

POJ 3076 Sudoku

最新文章

热门文章
