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;
比较了很久,分析不出为什么我自己写的效率差这么多,请各位帮忙指点一下,感谢!
上一篇: 后端开发面试题(三)Mybatis篇