poj 2676 Sudoku（DFS+回溯+剪枝）

2676 -- Sudoku (poj.org)

#include<iostream>
#include<cstring>
using namespace std;
int t,row[10][10],col[10][10],grid[10][10],map[10][10];
bool DFS(int r,int c){
    if(r==10) return true;
    bool flag=false;
    if(map[r][c]){
        if(c==9) flag=DFS(r+1,1);
        else flag=DFS(r,c+1);
        return flag;
    }else{
        int k=((r-1)/3)*3+(c-1)/3+1;
        for(int i=1;i<=9;i++){
            if(!row[r][i]&&!col[c][i]&&!grid[k][i]){
                map[r][c]=i;
                row[r][i]=true;
                col[c][i]=true;
                grid[k][i]=true;
                if(c==9) flag=DFS(r+1,1);
                else flag=DFS(r,c+1);
                if(!flag){
                    map[r][c]=false;
                    row[r][i]=false;
                    col[c][i]=false;
                    grid[k][i]=false;
                }else return flag;
            }
        }
    }
    return false;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--){
        memset(row,0,sizeof(row));    
        memset(col,0,sizeof(col));
        memset(grid,0,sizeof(grid));
        for(int i=1;i<=9;i++){
            for(int j=1;j<=9;j++){
                char ch;
                cin>>ch;
                map[i][j]=ch-'0';
                if(map[i][j]){
                    row[i][map[i][j]]=true;
                    col[j][map[i][j]]=true;
                    int k=((i-1)/3)*3+(j-1)/3+1;
                    grid[k][map[i][j]]=true;
                }
            }
        }
        DFS(1,1);
        for(int i=1;i<=9;i++){
            for(int j=1;j<=9;j++){
                cout<<map[i][j];
            }
            cout<<endl;
        }
    }    
    return 0;
}