POJ 2676 Sudoku
【摘要】 题目链接~~>
做题感悟:第一次做时直接暴力就水过,但是在看别人解题报告时有人竟然用 0 ms 过了,很无语。
解题思路:1 ) 直接暴力 耗时大约:1400ms 2 ) 用三个标记数组标记 耗时大约:400ms 3 ) 用精确覆盖算法 耗时大约:...
做题感悟:第一次做时直接暴力就水过,但是在看别人解题报告时有人竟然用 0 ms 过了,很无语。
解题思路:1 ) 直接暴力 耗时大约:1400ms 2 ) 用三个标记数组标记 耗时大约:400ms 3 ) 用精确覆盖算法 耗时大约:0 ms ,但是倒着填数比正着填要耗时短一般为 16 ms 就过了,估计是数据问题。那就说一下第二种方法吧,第三种没接触:用三个数组 row[ ][ ] col[ ][ ] vis[ ][ ] 分别标记一个数在第几行,第几列,第几个小正方形出现过,于是查询的时候就是O( 1 ) 的复杂度,至于row col 好标记,至于列 用 i / 3 * 3 + j/ 3 就是第几格小正方形(找规律)。
代码(逆向):
-
#include<stdio.h>
-
#include<iostream>
-
#include<map>
-
#include<stack>
-
#include<string>
-
#include<string.h>
-
#include<stdlib.h>
-
#include<math.h>
-
#include<vector>
-
#include<queue>
-
#include<algorithm>
-
using namespace std ;
-
#define LEN sizeof(struct node)
-
#define lld __int64
-
const double PI = 3.1415926535898 ;
-
const int INF = 99999999 ;
-
const double esp = 1e-8 ;
-
const long long mod= 1000 ;
-
const int MX = 15 ;
-
bool flag ;
-
int g[MX][MX] ;
-
bool row[MX][MX],col[MX][MX],vis[MX][MX] ;
-
void dfs(int x,int y)
-
{
-
if(flag) return ;
-
if(y==-1)
-
{
-
x-- ;
-
y=8 ;
-
}
-
if(x==-1&&y==8)
-
{
-
for(int i=0 ;i<9 ;i++)
-
{
-
for(int j=0 ;j<9 ;j++)
-
printf("%d",g[i][j]) ;
-
printf("\n") ;
-
}
-
flag=true ;
-
return ;
-
}
-
if(g[x][y])
-
dfs(x,y-1) ;
-
else
-
{
-
for(int i=1 ;i<=9 ;i++)
-
if(!row[x][i]&&!col[y][i]&&!vis[3*(x/3)+y/3][i])
-
{
-
row[x][i]=true ;
-
col[y][i]=true ;
-
vis[3*(x/3)+y/3][i]=true ;
-
g[x][y]=i ;
-
dfs(x,y-1) ;
-
g[x][y]=0 ;
-
row[x][i]=false ;
-
col[y][i]=false ;
-
vis[3*(x/3)+y/3][i]=false ;
-
}
-
}
-
}
-
int main()
-
{
-
int Tx ;
-
char s[MX] ;
-
scanf("%d",&Tx) ;
-
while(Tx--)
-
{
-
memset(row,false,sizeof(vis)) ;
-
memset(col,false,sizeof(col)) ;
-
memset(g,0,sizeof(g)) ;
-
memset(vis,false,sizeof(vis)) ;
-
int k,x ;
-
for(int i=0 ;i<9 ;i++)
-
{
-
scanf("%s",s) ;
-
for(int j=0 ;j<9 ;j++)
-
{
-
g[i][j]=x=s[j]-'0' ;
-
if(x)
-
{
-
k=3*(i/3)+j/3 ;
-
row[i][x]=true ;
-
col[j][x]=true ;
-
vis[k][x]=true ;
-
}
-
}
-
}
-
flag=false ;
-
dfs(8,8) ;
-
}
-
return 0 ;
-
}
文章来源: blog.csdn.net,作者:Linux猿,版权归原作者所有,如需转载,请联系作者。
原文链接:blog.csdn.net/nyist_zxp/article/details/23018183
推荐
![](https://res.hc-cdn.com/ecology/9.3.128/v2_resources\images\global\blog-dialog.png)
华为开发者空间发布
让每位开发者拥有一台云主机
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)