HDOJ5547 SudoKu

題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=5547

題目大意：填數獨。。。

思路：爆搜

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
bool row[5][5],col[5][5],siz[5][5];
int G[5][5];
bool flag;
int Num(int x,int y){
    if(x<=2&&y<=2) return 1;
    if(x<=2&&y>2) return 2;
    if(x>2&&y<=2) return 3;
    if(x>2&&y>2) return 4;
}
void dfs(int x,int y){
    if(y>4&&x==4){
        flag=true;
        return ;
    }
    if(flag) return ;
    if(y>4) x++,y=1;
    if(G[x][y]) {
        dfs(x,y+1);
        return;
    }
    if(flag) return ;
    for(int i=1;i<=4;i++){
        if(!row[x][i]&&!col[y][i]&&!siz[Num(x,y)][i]){
            G[x][y]=i;
            row[x][i]=col[y][i]=siz[Num(x,y)][i]=true;
            dfs(x,y+1);
            if(flag) return ;
            G[x][y]=0;
            row[x][i]=col[y][i]=siz[Num(x,y)][i]=false;
        }
    }
}
void init(){
    flag=false;
    memset(row,false,sizeof(row));
    memset(col,false,sizeof(col));
    memset(siz,false,sizeof(siz));
}
void solve(int T){
    printf("Case #%d:\n",T);
    init();
    for(int x=1;x<=4;x++){
        for(int y=1;y<=4;y++){
            char tmp;
            scanf(" %c",&tmp);
            if(tmp=='*'){
                G[x][y]=0;
            }
            else {
                G[x][y]=tmp-'0';
                int now=tmp-'0';
                row[x][now]=col[y][now]=siz[Num(x,y)][now]=true;
            }
        }
    }
    dfs(1,1);
    for(int i=1;i<=4;i++){
        for(int j=1;j<=4;j++){
            printf("%d",G[i][j]);
        }
        printf("\n");
    }
}
int main(){
    int T;
    //freopen("C:\\Users\\acm\\Desktop\\ACM\\out.txt","w",stdout);
    scanf("%d",&T);
    for(int i=1;i<=T;i++) solve(i);
}

?