POJ 2676 Sudoku

举报
Linux猿 发表于 2021/08/05 23:28:48 2021/08/05
【摘要】 题目链接~~> 做题感悟:第一次做时直接暴力就水过,但是在看别人解题报告时有人竟然用 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

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。