UESTC 1222 Sudoku

爆搜即可

/* ***********************************************
author        :
email         :[e-mail]
created time  :2015/12/1 15:46:23
file name     :main.cpp
************************************************ */

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

const int maxn=;
int r[maxn][maxn],c[maxn][maxn],q[maxn][maxn];
int T;
char Map[maxn][maxn];
int ans[maxn][maxn];
int Qx[maxn*maxn],Qy[maxn*maxn];
int tot;
int flag;

int F(int x,int y)
{
    if(x==||x==)
    {
        if(y<=) return ;
        else return ;
    }
    else
    {
        if(y<=) return ;
        else return ;
    }
}

void dfs(int Now)
{
    if(Now==tot)
    {
        flag=;
        return;
    }
    int nowX=Qx[Now];
    int nowY=Qy[Now];
    for(int i=;i<=;i++)
    {
        if(r[nowX][i]==&&c[nowY][i]==&&q[F(nowX,nowY)][i]==)
        {
            r[nowX][i]=c[nowY][i]=q[F(nowX,nowY)][i]=;
            ans[nowX][nowY]=i;
            dfs(Now+);
            if(flag) return;
            r[nowX][i]=c[nowY][i]=q[F(nowX,nowY)][i]=;
        }
    }
}

int main()
{
    scanf("%d",&T);
    for(int Case=;Case<=T;Case++)
    {
        memset(r,,sizeof r);
        memset(c,,sizeof c);
        memset(q,,sizeof q);
        tot=; flag=;
        for(int i=;i<;i++) scanf("%s",Map[i]);
        for(int i=;i<;i++)
        {
            for(int j=;j<;j++)
            {
                if(Map[i][j]=='*')
                {
                    ans[i][j]=-;
                    Qx[tot]=i;
                    Qy[tot]=j;
                    tot++;
                }
                else
                {
                    ans[i][j]=Map[i][j]-'';
                    r[i][ans[i][j]]=;
                    c[j][ans[i][j]]=;
                    q[F(i,j)][ans[i][j]]=;
                }
            }
        }
        flag=;
        dfs();
        printf("Case #%d:\n",Case);
        for(int i=;i<;i++)
        {
            for(int j=;j<;j++)
                printf("%d",ans[i][j]);
            printf("\n");
        }
    }
    return ;
}