第36届福州赛区1009 Squiggly Sudoku 解题报告

    裸的DLX，比一般的数独酷稍微复杂点的就是处理输入，先dfs一下，然后建十字链表。

    直接上代码了，跑得比较慢。

#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x7fffffff;
const int NN = 350;
const int MM = 750;
int n,m;    //列，行
int cntc[NN];
int L[NN*MM],R[NN*MM],U[NN*MM],D[NN*MM];
int C[NN*MM];   //列的头链表
int head;
int mx[MM][NN];
int O[MM],idx,idx2,O2[MM];
int ans[10][10];
int flags;

//删除列及其相应的行
void remove(int c)
{
    int i,j;
    L[R[c]] = L[c];
    R[L[c]] = R[c];
    for(i = D[c]; i != c; i = D[i])
    {
        for(j = R[i]; j != i; j = R[j])
        {
            U[D[j]] = U[j];
            D[U[j]] = D[j];
            cntc[C[j]]--;
        }
    }
}

//恢复列及其相应的行
void resume(int c)
{
    int i,j;
    R[L[c]] = c;
    L[R[c]] = c;
    for(i = D[c]; i != c; i = D[i])
    {
        for(j = R[i]; j != i; j = R[j])
        {
            U[D[j]] = j;
            D[U[j]] = j;
            cntc[C[j]]++;
        }
    }
}

void dfs()
{
    int i,j,c;
    if(flags > 1)
        return;
    if(R[head] == head)
    {
        flags++;
        idx2 = idx;
        for(i = 0; i < idx; i++)
            O2[i] = O[i];
        return;
    }
    int min = INF;
    for(i = R[head]; i != head; i = R[i])
    {
        if(cntc[i] < min)
        {
            min = cntc[i];
            c = i;
        }
    }
    remove(c);
    for(i = D[c]; i != c; i = D[i])
    {
        //i是某点的序号，将该点所在行的行号保存
        O[idx++] = (i-1)/n;
        for(j = R[i]; j != i; j = R[j])
            remove(C[j]);
        dfs();
        if(flags > 1)
            return;
        for(j = L[i]; j != i; j = L[j])
            resume(C[j]);
        idx--;
    }
    resume(c);
}

void init()
{
    idx = idx2 = head = 0;
    flags = 0;
    for (int i = 0; i <= n; i++)
    {
        C[i] = i;
        D[i] = i;
        U[i] = i;
        cntc[i] = 0;
        R[i] = (i+1)%(n + 1);
        L[(i+1)%(n + 1)] = i;
    }
}

void insert(int r, int *mk)
{
    int now, pre, first;
    for(int j = 0; j < 4; j++)
    {
        cntc[mk[j]]++;
        now = r*n+mk[j];
        pre = U[mk[j]];
        C[now] = mk[j];
        D[pre] = now;
        U[now] = pre;
        D[now] = mk[j];
        U[mk[j]] = now;
    }
    pre = first = -1;
    for (int i = 0; i < 4; i++)
    {
        now = r*n+mk[i];
        if(pre == -1)
            first = now;
        else
        {
            R[pre] = now;
            L[now] = pre;
        }
        pre = now;
    }
    if(first != -1)
    {
        R[pre] = first;
        L[first] = pre;
    }
}

void print()
{
    int i,j;
    int x,y,k;
    for(i = 0; i < idx2; i++)
    {
        int r = O2[i];
        k = r%9;
        if(k==0) k = 9;
        int num = (r - k)/9 + 1;
        y = num%9;
        if(y == 0) y = 9;
        x = (num-y)/9 + 1;
        ans[x][y] = k;
    }
    if(flags == 0)
        printf("No solution\n");
    else
    {
        if(flags > 1)
            printf("Multiple Solutions\n");
        else
        {
            for(i = 1; i <= 9; i++)
            {
                for(j = 1; j <= 9; j++)
                    printf("%d",ans[i][j]);
                printf("\n");
            }
        }
    }
}
int d[4] = {128,64,32,16};
int dir[4][2] = {{0,-1},{1,0},{0,1},{-1,0}};
int mp[10][10];

struct Point
{
    bool flag[4];   //左 下 右 上
    int seq;
    int value;
}p[10][10];

bool change = 0;

void floodfill(int i, int j, int seq)
{
    if(p[i][j].seq > 0)
        return;
    p[i][j].seq = seq;
    for(int k = 0; k < 4; k++)
    {
        if(p[i][j].flag[k])
            continue;
        int x = i + dir[k][0];
        int y = j + dir[k][1];
        if(x>=1&&x<=9&&y>=1&&y<=9&&p[x][y].seq==0)
        {
            change = 1;
            floodfill(x,y,seq);
        }
    }
}

int main()
{
    int i,j,k;
    int cases;
    scanf("%d",&cases);
    int tt = 0;
    while(cases--)
    {
        for(i = 1; i <= 9; i++)
        {
            for(j = 1; j <= 9; j++)
            {
                p[i][j].seq = 0;
                for(k = 0; k < 4; k++)
                    p[i][j].flag[k] = 0;
            }
        }
        for(i = 1; i <= 9; i++)
            for(j = 1; j <= 9; j++)
            {
                scanf("%d",&mp[i][j]);
                for(k = 0; k < 4; k++)
                {
                    if(mp[i][j] < 16)
                    {
                        p[i][j].value = mp[i][j];
                        break;
                    }
                    int t = mp[i][j]-d[k];
                    if(t >= 0)
                    {
                        p[i][j].flag[k] = 1;
                        mp[i][j] = t;
                    }
                }
                if(k == 4)
                    p[i][j].value = mp[i][j];
            }
        int seq = 1;
        for(i = 1; i <= 9; i++)
        {
            for(j = 1; j <= 9; j++)
            {
                change = 0;
                floodfill(i,j,seq);
                if(change)
                    seq++;
            }
        }
        n = 324;
        m = 729;
        init();
        for(i = 1; i <= 9; i++)
        {
            for(j = 1; j <= 9; j++)
             {
                int t = (i-1)*9 + j;
                if(p[i][j].value == 0)
                {
                    for(k = 1; k <= 9; k++)
                    {
                        int tvec[5];
                        tvec[0] = t;
                        tvec[1] = (81+(i-1)*9+k);
                        tvec[2] = (162+(j-1)*9+k);
                        tvec[3] = (243+(p[i][j].seq-1)*9+k);
                        insert(9*(t-1)+k, tvec);
                    }
                }
                else
                {
                    int tvec[5];
                    k = p[i][j].value;
                    tvec[0] = t;
                    tvec[1] = (81+(i-1)*9+k);
                    tvec[2] = (162+(j-1)*9+k);
                    tvec[3] = (243+(p[i][j].seq-1)*9+k);
                    insert(9*(t-1)+k, tvec);
                }
            }
        }
        printf("Case %d:\n",++tt);
        dfs();
        print();
    }
    return 0;
}