HDU 4069 Squiggly Sudoku(DLX 精确覆盖)解题报告

2017-05-12 1,856 次浏览 解题报告

解题思路

此题是解异性数独,代码写起来比较繁琐。

首先按照题意求连通块,转化为普通数独。然后用正常求解数独的 DLX 精确覆盖算法即可解决。

另外应注意一旦计算出多解时要及时返回,防止超时。

参考代码

#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;

const int N = 9*9*9;
const int M = 9*9*4;

struct DLX {
    int l, r, u, d;
    int row, col;
} dlx[(N+1)*(M+1)+M+1];

struct row_info {
    int head;
    int row, col, value; // original info
} rinfo[N+1];

struct info {
    int value;
    bool banned_dirt[4];
    int idx;
} a[9][9];

int sz[M+1], idx, bidx, ans[9][9], final_ans[9][9], ans_cnt;
int dirt[4][2] = {
    {-1, 0}, {0, 1}, {1, 0}, {0, -1}
};
bool hasr[9][10], hasc[9][10], hasb[9][10];

void Init(int m) {
    for(int i=0; i<=m; ++i) {
        dlx[i].u = dlx[i].d = i;
        dlx[i+1].l = i;
        dlx[i].r = i+1;
        sz[i] = 0;
    }
    dlx[m].r = 0;
    dlx[0].l = m;
    idx = m+1;
}

void Insert(int r, int c) {
    sz[c]++;
    // U/D
    dlx[dlx[c].u].d = idx;
    dlx[idx].u = dlx[c].u;
    dlx[idx].d = c;
    dlx[c].u = idx;
    dlx[idx].row = r;
    dlx[idx].col = c;
    // L/R
    if(rinfo[r].head == -1)
        rinfo[r].head = dlx[idx].l = dlx[idx].r = idx;
    else {
        dlx[dlx[rinfo[r].head].l].r = idx;
        dlx[idx].l = dlx[rinfo[r].head].l;
        dlx[idx].r = rinfo[r].head;
        dlx[rinfo[r].head].l = idx;
    }
    idx++;
}

void Remove(int c) {
    // Column
    dlx[dlx[c].l].r = dlx[c].r;
    dlx[dlx[c].r].l = dlx[c].l;
    // Row
    for(int i=dlx[c].d; i!=c; i=dlx[i].d) {
        for(int j=dlx[i].r; j!=i; j=dlx[j].r) {
            dlx[dlx[j].u].d = dlx[j].d;
            dlx[dlx[j].d].u = dlx[j].u;
            sz[dlx[j].col]--;
        }
    }
}

void Resume(int c) {
    // Column
    dlx[dlx[c].l].r = c;
    dlx[dlx[c].r].l = c;
    // Row
    for(int i=dlx[c].u; i!=c; i=dlx[i].u) {
        for(int j=dlx[i].l; j!=i; j=dlx[j].l) {
            dlx[dlx[j].u].d = j;
            dlx[dlx[j].d].u = j;
            sz[dlx[j].col]++;
        }
    }
}

void Dance() {
    if(ans_cnt > 1) return;
    if(dlx[0].r == 0) {
        ans_cnt++;
        if(ans_cnt == 1) {
            for(int i=0; i<9; ++i) {
                for(int j=0; j<9; ++j) {
                    final_ans[i][j] = ans[i][j];
                }
            }
        }
        return;
    }
    else {
        int minsz = 0x3f3f3f3f, c;
        for(int i=dlx[0].r; i!=0; i=dlx[i].r) {
            if(sz[i] == 0) return;
            if(sz[i] < minsz) {
                minsz = sz[i];
                c = i;
                if(minsz == 1) break;
            }
        }
        Remove(c);
        for(int i=dlx[c].d; i!=c; i=dlx[i].d) {
            ans[rinfo[dlx[i].row].row][rinfo[dlx[i].row].col] = rinfo[dlx[i].row].value;
            for(int j=dlx[i].r; j!=i; j=dlx[j].r) {
                Remove(dlx[j].col);
            }
            Dance();
            for(int j=dlx[i].l; j!=i; j=dlx[j].l) {
                Resume(dlx[j].col);
            }
        }
        Resume(c);
    }
}

bool Judge(int x, int y) {
    if(x>=0 && x<9 && y>=0 && y<9)
        return true;
    else return false;
}

void DFS(int x, int y) {
    a[x][y].idx = bidx;
    for(int i=0; i<4; ++i) {
        if(a[x][y].banned_dirt[i]) continue;
        int nx = x + dirt[i][0];
        int ny = y + dirt[i][1];
        if(Judge(nx, ny) && a[nx][ny].idx==-1) {
            a[nx][ny].idx = bidx;
            DFS(nx, ny);
        }
    }
}

int main(int argc, char const *argv[]) {
    int t, bin;
    scanf("%d", &t);
    for(int cases=1; cases<=t; ++cases) {
        printf("Case %d:\n", cases);
        memset(a, 0, sizeof a);
        for(int i=0; i<9; ++i) {
            for(int j=0; j<9; ++j) {
                a[i][j].idx = -1;
                scanf("%d", &bin);
                stack<int> s;
                for(int k=0; k<4; ++k) {
                    s.push(bin&1);
                    bin >>= 1;
                }
                while(!s.empty()) {
                    a[i][j].value = a[i][j].value*2 + s.top();
                    s.pop();
                }
                for(int k=0; k<4; ++k) {
                    a[i][j].banned_dirt[k] = bin & 1;
                    bin >>= 1;
                }
            }
        }
        bidx = 0;
        for(int i=0; i<9; ++i) {
            for(int j=0; j<9; ++j) {
                if(a[i][j].idx == -1) {
                    DFS(i, j);
                    bidx++;
                }
            }
        }
        memset(hasr, false, sizeof hasr);
        memset(hasc, false, sizeof hasc);
        memset(hasb, false, sizeof hasb);
        for(int i=0; i<9; ++i) {
            for(int j=0; j<9; ++j) {
                if(a[i][j].value) {
                    hasr[i][a[i][j].value] = true;
                    hasc[j][a[i][j].value] = true;
                    hasb[a[i][j].idx][a[i][j].value] = true;
                }
            }
        }
        Init(M);
        int n = 0;
        for(int i=0; i<9; ++i) {
            for(int j=0; j<9; ++j) {
                int sidx = i*9 + j;
                if(a[i][j].value) {
                    rinfo[n].row = i;
                    rinfo[n].col = j;
                    rinfo[n].value = a[i][j].value;
                    rinfo[n].head = -1;
                    Insert(n, 1 + sidx);
                    Insert(n, 81 + i*9+a[i][j].value);
                    Insert(n, 162 + j*9+a[i][j].value);
                    Insert(n, 243 + a[i][j].idx*9+a[i][j].value);
                    n++;
                }
                else {
                    for(int k=1; k<=9; ++k) {
                        if(!hasr[i][k] && !hasc[j][k] && !hasb[bidx][k]) {
                            rinfo[n].row = i;
                            rinfo[n].col = j;
                            rinfo[n].value = k;
                            rinfo[n].head = -1;
                            Insert(n, 1 + sidx);
                            Insert(n, 81 + i*9+k);
                            Insert(n, 162 + j*9+k);
                            Insert(n, 243 + a[i][j].idx*9+k);
                            n++;
                        }
                    }
                }
            }
        }
        ans_cnt = 0;
        Dance();
        if(ans_cnt == 0) printf("No solution\n");
        if(ans_cnt == 1) {
            for(int i=0; i<9; ++i) {
                for(int j=0; j<9; ++j) {
                    printf("%d", final_ans[i][j]);
                }
                printf("\n");
            }
        }
        if(ans_cnt == 2) printf("Multiple Solutions\n");
    }
    
    return 0;
}

bLue 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。
本文地址:https://dreamer.blue/blog/post/2017/05/12/hdu-4069.dream

还不快抢沙发

添加新评论