欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

OpenJudge上2982:Sudoku代码效率问题

程序员文章站 2022-03-14 09:55:06
...

原题地址:http://bailian.openjudge.cn/practice/2982/

我个人写的代码是用指针指向二维字符数组,通过指针从数组开始逐一去判断每个位置上的数字是否合适,没有采用判断每一行到头转换下一行的方法,算法测试没有问题,但是不知道为什么效率就比别人的低。

我自己写的代码:

#include <iostream>
#include <cstring>
using namespace std;
char s[9][9];									//f用来表示是否找到一个答案 
int f;
bool judge1(int i,int j,char c){                  //单独判断小九宫格里数字是否重复函数 
	char*p=s[i*3]+j*3;
	for(int k=0;k<3;k++){
		for(int t=0;t<3;t++)
			if(p[9*k+t]==c) return false;
	}
	return true;
}
bool judge(int k,char c){				//判断行、列和小九宫格受否和要设置的数字重复 
	int i=k/9;							//i、j分别代表当前行、列编号 
	int j=k%9;
	for(int p=0;p<9;p++){
		if(s[i][p]==c) return false;
		if(s[p][j]==c) return false;
	}
	int ii=i/3;							//ii、jj用来定位当前位置所属的小九宫格位置 
	int jj=j/3;
	if(judge1(ii,jj,c)) return true;	//单独判断小九宫格函数 
	else return false;
}
void dfs(char*p){						//用指针来指向连续的二维数组 
	if(f) return;						//已经有答案就结束; 
	if(p-s[0]==80&&*p!='0'){				
		char*q=s[0];
		for(int i=0;i<81;i++){
			if(i!=0&&i%9==0) cout<<endl;
			cout<<q[i];
		}
		cout<<endl;
		f=1;
		return ;
	}
	if(*p!='0') dfs(p+1);
	if(*p=='0'){
		for(int i=1;i<=9;i++){						//从1到9尝试在P指针处放置数字 
			if(judge(p-s[0],i+'0')){
//				cout<<p-s[0]<<" "<<i<<endl;
				*p=i+'0';
				if(p-s[0]!=80)
					dfs(p+1);
				else dfs(p);
				if(f) return;
			}	
		}
		*p='0';
	}
	return ;
}
int main()
{
	int n;

	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<9;j++){
			for(int k=0;k<9;k++)
				cin>>s[j][k];
			getchar();
		}
		char*p=s[0];
		f=0;
		dfs(p);
	}
	return 0;
}

提交网站之后结果正确,但是时间大概是650ms;

参考其他人写的代码:https://blog.csdn.net/lovemylife1234/article/details/72026690?fps=1&locationNum=3

提交之后时间就4ms;

比较了很久,分析不出为什么我自己写的效率差这么多,请各位帮忙指点一下,感谢!

相关标签: 程序设计实习MOOC