P1784为什么没有结果
  • 板块P1784 数独
  • 楼主YONIC
  • 当前回复6
  • 已保存回复6
  • 发布时间2022/5/15 11:34
  • 上次更新2023/10/28 01:24:00
查看原帖
P1784为什么没有结果
536439
YONIC楼主2022/5/15 11:34
#include<bits/stdc++.h>
using namespace std;
int a[10][10],c[10][10],v[10][10],m[10][10];
int matrix(int x,int y){return (x-1)/3*3+(y-1)/3*3+1;}
void output(){
	for(int i=1;i<=9;++i){
		for(int j=1;j<=9;++j) printf("%d ",a[i][j]);
		puts("");
	}
}
void DFS(int x,int y){
	if(a[x][y]){
		if(x==9&&y==9){
			output();
			return;
		}
		if(y==9) DFS(x+1,1);
		if(y!=9) DFS(x,y+1);
		return;
	}
	for(int i=1;i<=9;++i){
		if(c[x][i]||v[y][i]||m[matrix(x,y)][i]) continue;
		a[x][y]=i;
		c[x][i]=v[y][i]=m[matrix(x,y)][i]=1;
		if(x==9&&y==9){
			output();
			return;
		}
		if(y==9) DFS(x+1,1);
		if(y!=9) DFS(x,y+1);
		a[x][y]=0;
		c[x][i]=v[y][i]=m[matrix(x,y)][i]=0;
	}
}
int main(){
	for(int i=1;i<=9;++i){
		for(int j=1;j<=9;++j){
			scanf("%d",a[i]+j);
			c[i][a[i][j]]=1;
			v[j][a[i][j]]=1;
			m[matrix(i,j)][a[i][j]]=1;
		}
	}
    DFS(1,1);
	return 0;
}
2022/5/15 11:34
加载中...