20200201新的一个月继续写搜索 POJ - 2676 Sudoku

#include <iostream>
#include <cstring>
#include <queue>
#include <math.h>
#include <map>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[10][10];
int line[10][10],row[10][10],block[10][10];
int n,m,flag;
struct point{int l,x,y;};
typedef pair<point,int>p;
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};
point now,newo,ende;
queue<p> qu;
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}
    return x*f;
}

inline void clean(){
    memset(a,0,sizeof(a));
    memset(line,0,sizeof(line));
    memset(row,0,sizeof(row));
    memset(block,0,sizeof(block));
    flag=0;
}

int go(int i,int j){
    if(i>0 && i<4 && j>0 && j<4)return 1;
    if(i>3 && i<7 && j>0 && j<4)return 2;
    if(i>6 && i<10 && j>0 && j<4)return 3;
    if(i>0 && i<4 && j>3 && j<7)return 4;
    if(i>3 && i<7 && j>3 && j<7)return 5;
    if(i>6 && i<10 && j>3 && j<7)return 6;
    if(i>0 && i<4 && j>6 && j<10)return 7;
    if(i>3 && i<7 && j>6 && j<10)return 8;
    return 9;
}

void print(){
    for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++)
            cout<<a[i][j];
        cout<<endl;
    }
}

void dfs(int i,int j){
    if(!flag){
        if(i==9){
            if(j==9 && a[i][j])
                j++;
            if(j==10)
                {print();flag=1;}
        }
        if(j>9){i++,j=1;}
        if(!a[i][j]){
            for(int p=1;p<=9;p++){
                if(!row[i][p] && !line[j][p] && !block[go(i,j)][p]){
                    a[i][j]=p,line[j][p]=1,row[i][p]=1,block[go(i,j)][p]=1;
                    dfs(i,j+1);
                    a[i][j]=0,row[i][p]=0,line[j][p]=0,block[go(i,j)][p]=0;
                }
            }
            return;
        }
        dfs(i,j+1);
    }
}

int main()
{
	n=read();
	char ll;
	int temp;
	while(n--){
        clean();
        for(int j=1;j<=9;j++){
            for(int i=1;i<=9;i++){
                ll=getchar();
                temp=ll-‘0‘;
                a[j][i]=temp;line[i][temp]=1;row[j][temp]=1;block[go(j,i)][temp]=1;
            }
            ll=getchar();
        }
        dfs(1,1);
	}
	return 0;
}