HDOJ 4069 Squiggly Sudoku 精确覆盖+搜索

//HDOJ 4069 Squiggly Sudoku 精确覆盖+搜索
/*
题意：数独变形 
	  9块弯弯曲曲的区域 每块有9个小格
	  往这81个格子里面填写1-9的数字，使得每行，每列，每个区域都含有1、2、3...9

思路：先搜索标记出每一块 再精确覆盖

*/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
#define INF 0x7FFFFFFF
#define N 750
#define M 350
#define V N*M

int n, m, size, row, cnt;
int L[V], R[V], U[V], D[V], C[V] , X[V];
int S[M], Q[N] , H[N];
int s[10][10];
bool map[100][100],vis[N];
int dir[][2] = {0,-1,1,0,0,1,-1,0};
int bx[] = {128,64,32,16};
int color[10][10],ans[N];
struct node{
    int x,y;
};
void init(){
    int i;
    for (i = 0; i <= m; i++){
        S[i] = 0;
        L[i + 1] = i;
        R[i] = i + 1;
        U[i] = D[i] = i;
    }
    R[m] = 0;
    size = m + 1;
}
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[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;
            S[C[j]]++;
        }
    }
}
void Link(int r, int c){
    D[size] = D[c];
    U[size] = c;
    U[D[c]] = size;
    D[c] = size;
    if (H[r] < 0)
        H[r] = L[size] = R[size] = size;
    else{
        L[size] = H[r];
        R[size] = R[H[r]];
        L[R[H[r]]] = size;
        R[H[r]] = size;
    }
    S[c]++;
    C[size] = c;
    X[size++] = r;
}
bool Dance(){
    int i, j, c, temp;
    if (R[0] == 0){
        ++cnt;
        if(cnt == 1){
            for(i = j = 1; i <= row; ++i)
                if(vis[i])
                    ans[j++] = Q[i];
        }
        return cnt > 1;
    }
    for (temp = INF, i = R[0]; i; i = R[i]){
        if (S[i] < temp){
            c = i;
            temp = S[i];
        }
    }
    remove(c);
    for (i = D[c]; i != c; i = D[i]){
        vis[X[i]] = true;
        for (j = R[i]; j != i; j = R[j])
            remove(C[j]);
        if (Dance())
            return true;
        for (j = L[i]; j != i; j = L[j])
            resume(C[j]);
        vis[X[i]] = false;
    }
    resume(c);
    return false;
}
bool check(int x,int y){
    if(x>=1 && x<=9 && y>=1 && y<=9)
        return true;
    return false;
}
void Init(){
    int i,j,k,x,y;
    memset(map,false,sizeof(map));
    for(i = 1; i <= 9; ++i){
        for(j = 1; j <= 9; ++j){       
            scanf("%d",&s[i][j]);
            for(k = 0; k < 4; ++k){
                if(s[i][j] >= bx[k])
                    s[i][j] -= bx[k];
                else{
                    x = i + dir[k][0];
                    y = j + dir[k][1];
                    if(check(x,y))
                        map[(i-1)*9+j][(x-1)*9+y] = true;
                }
            }
        }
    }
}
void bfs(int x,int y,int c){
    int k;
    queue<node>Q;
    node p,q;
    p.x = x;
    p.y = y;
    Q.push(p);
    while(!Q.empty()){
        q = Q.front();
        Q.pop();
        for(k = 0; k < 4; ++k){
            p.x = q.x + dir[k][0];
            p.y = q.y + dir[k][1];
            if(check(p.x,p.y) && map[(q.x-1)*9+q.y][(p.x-1)*9+p.y] && color[p.x][p.y]==-1){
                color[p.x][p.y] = c;
                Q.push(p);
            }
        }
    }
}
void Color(){
    int i,j,num = 0;
    memset(color,-1,sizeof(color));
    for(i = 1; i <= 9; ++i)
        for(j = 1; j <= 9; ++j){
            if(color[i][j] == -1){
                color[i][j] = num;
                bfs(i,j,num);
                num++;
            }
        }
}
void Build(){
    init();
    int i,j,k;
    row = 0;
    for(i = 1; i <= 9; ++i){
        for(j = 1; j <= 9; ++j){
            if(s[i][j] == 0){
                for(k = 1; k <= 9; ++k){
                    H[++row] = -1;
                    Q[row] = k;
                    Link(row,(i-1)*9+k);
                    Link(row,81+(j-1)*9+k);
                    Link(row,162+color[i][j]*9+k);
                    Link(row,243+(i-1)*9+j);
                }
            }
            else{
                H[++row] = -1;
                k = s[i][j];
                Q[row] = k;
                Link(row,(i-1)*9+k);
                Link(row,81+(j-1)*9+k);
                Link(row,162+color[i][j]*9+k);
                Link(row,243+(i-1)*9+j);
            }
        }
    }
	
}
int main(){
    int T,i,j,num,ca = 1;
    int x,y;
    m = 324;
    scanf("%d",&T);
    while(T--){
        Init();
        Color();
        Build();
        memset(vis,false,sizeof(vis));
        cnt = 0;
        Dance();
        printf("Case %d:\n",ca++);
        if(cnt == 0)
            puts("No solution");
        else if(cnt > 1)
            puts("Multiple Solutions");
        else{
            num = 1;
            for(i = 1; i <= 9; ++i){
                for(j = 1; j <= 9; ++j){
                    printf("%d",ans[num]);
                    if(num%9 == 0)
                        puts("");
                    num++;
                }
            }
        }
    }
    return 0;
}