xhSong's Blog

原题

#include <cstdio>
#include <iostream>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <iterator>
#include <algorithm>


using namespace std;


int const N = 3;
int PN = N * N, QN = PN * PN;

/***最大行***/
#define MAXROW 1001
/***最大列***/
#define MAXCOL 1001

struct DancingLinksNode {
    /***结点所在的行列位置***/
    int r, c;
    /***结点的上下左右结点指针***/
    DancingLinksNode *U, *D, *L, *R;
};

/****备用结点****/
DancingLinksNode node[MAXROW * 101];
/****行头****/
DancingLinksNode row[MAXROW];
/****列头****/
DancingLinksNode col[MAXCOL];
/****表头****/
DancingLinksNode head;
/****使用了多少结点****/
int cnt;
/****列含有多少个域****/
int size[MAXCOL];
/****表的行与列变量****/
int m, n;
/****选择的行****/
int choice[MAXROW];

/****初始化，r, c分别表示表的大小***/
void init(int r, int c) {
    /****将可以使用的结点设为第一个****/
    cnt = 0;
    /****head结点的r,c分别表示表的大小,以备查****/
    head.r = r;
    head.c = c;
    /****初始化head结点****/
    head.L = head.R = head.U = head.D = &head;

    /***初始化列头***/
    for(int i = 0; i < c; ++i) {
        col[i].r = r;
        col[i].c = i;
        col[i].L = head.L;
        col[i].R = &head;
        col[i].L->R = col[i].R->L = &col[i];
        col[i].U = col[i].D = &col[i];
        size[i] = 0;
    }


    /***初始化行头,在删除的时候，如果碰到row[i].c  == c的情形应当被跳过***/
    for(int i = r - 1; i > -1; --i) {
        row[i].r = i;
        row[i].c = c;
        row[i].U = head.U;
        row[i].D = &head;
        row[i].U->D = row[i].D->U = &row[i];
        row[i].L = row[i].R = &row[i];
    }
}

/****增加一个结点,在原表中的位置为r行,c列***/
inline void addNode(int r, int c) {
    /****找一个未曾使用的结点****/
    DancingLinksNode *ptr = &node[cnt++];

    /****设置结点的行列号****/
    ptr->r = r;
    ptr->c = c;

    /****将结点加入双向链表中****/
    ptr->L = row[r].L;
    ptr->R = &row[r];
    ptr->L->R = ptr->R->L = ptr;

    ptr->U = col[c].U;
    ptr->D = &col[c];
    ptr->U->D = ptr->D->U = ptr;

    /****将size域加1****/
    ++size[c];
}

/****删除ptr所指向的结点的左右方向****/
inline void delLR(DancingLinksNode * ptr) {
    ptr->L->R = ptr->R;
    ptr->R->L = ptr->L;
}

/****删除ptr所指向的结点的上下方向****/
inline void delUD(DancingLinksNode * ptr) {
    ptr->U->D = ptr->D;
    ptr->D->U = ptr->U;
}

/****重置ptr所指向的结点的左右方向****/
inline void resumeLR(DancingLinksNode * ptr) {
    ptr->L->R = ptr->R->L = ptr;
}

/****重置ptr所指向的结点的上下方向****/
inline void resumeUD(DancingLinksNode * ptr) {
    ptr->U->D = ptr->D->U = ptr;
}

/****覆盖第c例***/
inline void cover(int c) {
    /**** c == n 表示头****/
    if(c == n) {
        return;
    }

    /****删除表头****/
    delLR(&col[c]);

    DancingLinksNode *R, *C;
    for(C = col[c].D; C != (&col[c]); C = C->D) {
        if(C->c == n)
            continue;
        for(R = C->L; R != C; R = R->L){
            if(R->c == n)
                continue;
            --size[R->c];
            delUD(R);
        }
        delLR(C);
    }

}

/****重置第c列****/
inline void resume(int c) {
    if(c == n)
        return;
    DancingLinksNode *R, *C;
    for(C = col[c].U; C != (&col[c]); C = C->U) {
        if(C->c == n)
            continue;
        resumeLR(C);
        for(R = C->R; R != C; R = R->R) {
            if(R->c == n)
                continue;
            ++size[R->c];
            resumeUD(R);
        }
    }

    /****把列头接进表头中****/
    resumeLR(&col[c]);
}

/****搜索核心算法,k表示搜索层数****/
int search(int k ＝ 0) {

    /***搜索成功,返回true***/
    if(head.L == (&head)) {
        return k;
    }
    /***c表示下一个列对象位置,找一个分支数目最小的进行覆盖***/
    int INF = (1<<30), c = -1;

    for(DancingLinksNode * ptr = head.L; ptr != (&head); ptr = ptr->L) {
        if(size[ptr->c] < INF) {
            INF = size[ptr->c];
            c = ptr->c;
        }
    }
    /***覆盖第c列***/
    cover(c);

    DancingLinksNode * ptr;

    for(ptr = col[c].D; ptr != (&col[c]); ptr = ptr->D) {
        DancingLinksNode *rc;
        ptr->R->L = ptr;
        choice[k] = ptr->r;
        for(rc = ptr->L; rc != ptr; rc = rc->L) {
            cover(rc->c);
        }
        ptr->R->L = ptr->L;
        int ans = search(k + 1);
        if(ans) {
            return ans;
        }
        ptr->L->R = ptr;
        for(rc = ptr->R; rc != ptr; rc = rc->R) {
            resume(rc->c);
        }
        ptr->L->R = ptr->R;
    }

    /***取消覆盖第c列***/
    resume(c);
    return 0;
}


void addPoss(int i, int j) {
    int x = i / PN, y = i % PN;
    addNode(i * PN + j, i);
    addNode(i * PN + j, QN * 1+ x * PN + j);
    addNode(i * PN + j, QN * 2 + y * PN + j);
    addNode(i * PN + j, QN * 3 + (x / N * N + y / N) * PN + j);
}

int main(int argc, char** argv) {
    char s[100];
    while(1) {
        scanf("%s", s);
        if(strcmp(s, "end") == 0) {
            break;
        }
        m = PN * QN, n = 4 * QN;
        init(m, n);
        for(int i = 0; i < QN; ++i) {
            if(s[i] == '.')  {
            	for(int j = 0; j < PN; ++j) addPoss(i, j);
            } else {
            	addPoss(i, s[i] - '1');
            }	
        }
        search();
        for(int i = 0; i < QN; i ++) {
            s[choice[i] / PN] = choice[i] % PN + '1';
        }
        puts(s);
    }
    return 0;
}