1 条题解

  • 0
    @ 2023-11-26 10:00:27
    #include<bits/stdc++.h>
    using namespace std;
    const int N = 10;
    int g[N][N], ans[N][N];
    int row[N][N], col[N][N], m[N][N];
    bool check(int x,int y, int t){
    	return !g[x][y] && !row[x][t] && !col[y][t] && !m[(x-1)/3*3 + (y-1)/3][t];
    }
    bool dfs(int x, int y){
    	if(g[x][y]){
    		if(y == 9){
    			if(dfs(x+1,1)) return true;
    		}else{
    			if(dfs(x,y+1)) return true;
    		}
    	}
    	if(x > 9){
    		for (int i = 1; i <= 9; i ++){
    			for(int j = 1; j <= 9; j ++){
    				cout << g[i][j] << " ";
    			}
    			cout << endl;
    		}
    		return true;
    	}
    	for(int i = 1; i <= 9; i ++){
    		if(check(x, y, i)){
    			row[x][i] = col[y][i] = m[(x-1)/3*3 + (y-1)/3][i] = true;
    			g[x][y] = i;
    			if(y == 9){
    				if(dfs(x+1,1)) return true;
    			}else{
    				if(dfs(x,y+1)) return true;
    			}
    			g[x][y] = 0;
    			row[x][i] = col[y][i] = m[(x-1)/3*3 + (y-1)/3][i] = false;
    		}
    	}
    	return false;
    }
    int main(){
    //	freopen("number.in","r",stdin);
    //	freopen("number.out","w",stdout);
    	for (int i = 1; i <= 9; i ++){
    		for (int j = 1; j <= 9; j ++){
    			char t;
    			cin >> t;
    			if(t == '*')
    				g[i][j] = 0;	
    			else{
    				g[i][j] = t - '0';
    				row[i][t-'0'] = col[j][t-'0'] = m[(i-1)/3*3 + (j-1)/3][t-'0'] = true;
    			}
    		}
    	}
    	dfs(1,1);
    	return 0;
    }
    

    信息

    ID
    550
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    (无)
    递交数
    64
    已通过
    21
    上传者