周报

数独深搜踩的坑

2020年4月2日

原题链接http://poj.org/problem?id=2676和http://poj.org/problem?id=2918

两题一样的改个输出格式就行

本来想跟着书练深搜剪枝，这是书上这一块第一题，本以为dfs会了其实还是不理解，前前后后改了四个版本，折腾了一个上午。

思路

poj上四个数独题，这是最简单的两道，优化想法来自书本。改边搜索顺序，先搜索已知数多的行。

丑陋的代码1.0

以每一格为一个阶段，出口和进一步深搜的先决条件没设计好。

递归返回到原来调用它的地方这里少了个col<=9竟会导致col无限递增，在这种情况下：某一行的最后一格是填过的，从这里递归下去遇到某一不合法状态又回溯到这里，然后这个if回溯的时候居然会再判断一次？

后补：网上别人的写法，所以其实是自己没分清情况，这一切都是一个美妙的误会……

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 25
#define INF 0x3f3f3f3f
using namespace std;
char mp[MAXN][MAXN];
struct Data{int row,cnt;}d[MAXN];
int visr[MAXN][MAXN],visc[MAXN][MAXN],flag;
bool cmp(Data a,Data b){
    return a.cnt>b.cnt;
}
void dfs(int deep,int row,int col){
//	printf("%d %d\n",row,col);
//	printf("%s\n",mp[row]+1);
	
//	if(col>10)return;
	if(col>=10&&deep<10)dfs(deep+1,d[deep+1].row,1);
	if(deep>=10&&col>=10){
		if(flag==0){
			for(int i=1;i<=9;++i){
            	printf("%s",mp[i]+1);
            	printf("\n");
        	}flag=1;
		}
		return;
	}
	if(mp[row][col]!='0'&&col<=9)dfs(deep,row,col+1);
	else{
		for(int k=1;k<=10;++k){
//			printf("%d %d\n",visr[row][2],visc[col][2]);
//			printf("k:%d %d %d %d %d\n",k,visr[row][k],visc[col][k],row,col);
			if(k==10)return;
            if(visr[row][k]||visc[col][k])continue;
            int mark=0,m=(row-1)/3*3+1,n=(col-1)/3*3+1;
            for(int i=m;i<m+3;++i)
            for(int j=n;j<n+3;++j)if(mp[i][j]==k+'0'){mark=1;break;}
            if(mark)continue;
            mp[row][col]=k+'0';
            visr[row][k]=visc[col][k]=1;
            dfs(deep,row,col+1);
            visr[row][k]=visc[col][k]=0,mp[row][col]='0';
        }
	}
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
    	memset(mp,0,sizeof(mp));
    	memset(visc,0,sizeof(visc));
    	memset(visr,0,sizeof(visr));
    	memset(d,0,sizeof(d));
        for(int i=1;i<=9;++i){scanf("%s",mp[i]+1);d[i].row=i;}
        for(int i=1;i<=9;++i)
            for(int j=1;j<=9;++j){
                if(mp[i][j]!='0'){visr[i][mp[i][j]-'0']=visc[j][mp[i][j]-'0']=2;d[i].cnt++;}    
            }
        sort(d+1,d+10,cmp);
        flag=0;
        dfs(1,d[1].row,1);
    }
}

丑陋的代码2.0

代码补贴了，出口和查重都搞好了，但是题目要求是输出一个答案（神啊能不能告诉蒟蒻dfs怎么break呜呜呜）不会弄瞎整，就是只输出第一个答案，后面继续dfs，妥妥的t了

丑陋的代码3.0

开始怀疑这个优化，换了个思路，以一整行为阶段，写不下去了，不会回溯，不贴代码了

丑陋的代码4.0

老思路，整个flag疯狂return，ac了，time当然是非常不好看

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 25
#define INF 0x3f3f3f3f
using namespace std;
char mp[MAXN][MAXN];
struct Data{int row,cnt;}d[MAXN];
int visr[MAXN][MAXN],visc[MAXN][MAXN],flag;
bool cmp(Data a,Data b){
    return a.cnt>b.cnt;
}
void dfs(int deep,int row,int col){
//	printf("%d %d\n",row,col);
//	printf("%s\n",mp[row]+1);
	
//	if(col>10)return;
    if(flag) return;
	if(col>=10&&deep<10)dfs(deep+1,d[deep+1].row,1);
	if(deep>=10&&col>=10){
		if(flag==0){
			for(int i=1;i<=9;++i){
            	printf("%s",mp[i]+1);
            	printf("\n");
        	}flag=1;
		}
		return;
	}
	if(flag) return;
	if(mp[row][col]!='0'&&col<=9)dfs(deep,row,col+1);
	else{
		for(int k=1;k<=10;++k){
//			printf("%d %d\n",visr[row][2],visc[col][2]);
//			printf("k:%d %d %d %d %d\n",k,visr[row][k],visc[col][k],row,col);
			if(k==10)return;
            if(visr[row][k]||visc[col][k])continue;
            int mark=0,m=(row-1)/3*3+1,n=(col-1)/3*3+1;
            for(int i=m;i<m+3;++i)
            for(int j=n;j<n+3;++j)if(mp[i][j]==k+'0'){mark=1;break;}
            if(mark)continue;
            mp[row][col]=k+'0';
            visr[row][k]=visc[col][k]=1;
            if(flag) return;
            dfs(deep,row,col+1);
            if(flag) return;
            visr[row][k]=visc[col][k]=0,mp[row][col]='0';
        }
        if(flag) return;
	}
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
    	memset(mp,0,sizeof(mp));
    	memset(visc,0,sizeof(visc));
    	memset(visr,0,sizeof(visr));
    	memset(d,0,sizeof(d));
        for(int i=1;i<=9;++i){scanf("%s",mp[i]+1);d[i].row=i;}
        for(int i=1;i<=9;++i)
            for(int j=1;j<=9;++j){
                if(mp[i][j]!='0'){visr[i][mp[i][j]-'0']=visc[j][mp[i][j]-'0']=2;d[i].cnt++;}    
            }
        sort(d+1,d+10,cmp);
        flag=0;
        dfs(1,d[1].row,1);
    }
}

啊，神犇是怎么做到2676time0ms的，以后有空接着优化。嗯…大概……

Views: 148

发表评论