题解 | #Sudoku#

这个小方块的bug我找了好久我去一口老血

#include <algorithm>
#include <vector>

using namespace std;

void dfs(vector<vector<int>> &v, vector<vector<bool>> &row,
          vector<vector<bool>> &col, vector<vector<bool>> &matrix,
         const vector<pair<int,int>> &spaces,int index,bool &valid){
    if(index==spaces.size()){
        valid =true;
        return;
    }
    int x = spaces[index].first;
    int y = spaces[index].second;
    int m = ((x+2)/3-1)*3+(y+2)/3;//这里刚开始有点抽没把关系找出啦
    for(int i =1;i<10&&!valid;i++){
        if(!row[x][i]&&!col[y][i]&&!matrix[m][i]){
            row[x][i]=true;
            col[y][i]=true;
            matrix[m][i]=true;//就是这里的bug让我找了好久，吐血。
            v[x][y]=i;
            dfs(v,row,col,matrix,spaces,index+1,valid);
            row[x][i]=false;
            col[y][i]=false;
            matrix[m][i]=false;
        }
    }
    return ;
    
}

int main() {
    vector<vector<int>> v(10,vector<int>(10,0));
    vector<vector<bool>> row(10,vector<bool>(10,false));
    vector<vector<bool>> col(10,vector<bool>(10,false));
    vector<vector<bool>> matrix(10,vector<bool>(10,false));
    vector<pair<int,int>> spaces;
    int temp = 0;
    int m;
    for(int i = 1;i<10;i++){
        for(int j = 1;j<10;j++){
            m = ((i+2)/3-1)*3+(j+2)/3;
            cin>>temp;
            if(temp==0){
                spaces.push_back(make_pair(i, j));
            }
            else{
            row[i][temp] = true;
            col[j][temp] = true;
            matrix[m][temp] =true;
            }
            v[i][j]=temp;
        }
    }//for
    bool valid =false;
    dfs(v,row,col,matrix,spaces,0,valid);
    
    for(int i = 1;i<10;i++){
        
        for(int j = 1;j<10;j++){
            cout<<v[i][j]<<' ';
        }
        cout<<endl;
    }
}