2 TLE!!!
  • 板块P1784 数独
  • 楼主MoonCake2011
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/2/9 22:18
  • 上次更新2023/10/24 01:16:56
查看原帖
2 TLE!!!
886055
MoonCake2011楼主2023/2/9 22:18
#include<bits/stdc++.h>
using namespace std;
#define r(x) ((x)-1)/9+1
#define c(x) ((x)-1)%9+1
#define b(x) (r(x)-1)/3*3+(c(x)-1)/3+1
int a[110];
int p[110];
int row[15][15],col[15][15],block[15][15];
void print(){
	for(int i=1;i<=81;i++){
		if(p[i]!=0)
			a[i]=p[i];
	}
	for(int i=1;i<=81;i++){
		cout<<a[i]<<" ";
		if(i%9==0) puts("");
	}
}
void dfs(int x){
	if(x>81){
		print();
		exit(0);
	}
	if(p[x]!=0) dfs(x+1);
	for(int i=9;i>=1;i--){
		if(row[r(x)][i]==0 && col[c(x)][i]==0 && block[b(x)][i]==0){
			row[r(x)][i]=1,col[c(x)][i]=1,block[b(x)][i]=1;
			a[x]=i;
			dfs(x+1);
			row[r(x)][i]=0,col[c(x)][i]=0,block[b(x)][i]=0;
			a[x]=0;
		}
	}
	return;
}
int main() {
	for(int i=1;i<=81;i++){
		int x;
		cin>>x;
		if(x!=0){
			p[i]=x;
			row[r(i)][x]=1,col[c(i)][x]=1,block[b(i)][x]=1;
			a[i]=x;
		} 
	}
	dfs(1);
	return 0;
}
2023/2/9 22:18
加载中...