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 就是第几格小正方形(找规律)。

代码(逆向):


  
  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<map>
  4. #include<stack>
  5. #include<string>
  6. #include<string.h>
  7. #include<stdlib.h>
  8. #include<math.h>
  9. #include<vector>
  10. #include<queue>
  11. #include<algorithm>
  12. using namespace std ;
  13. #define LEN sizeof(struct node)
  14. #define lld __int64
  15. const double PI = 3.1415926535898 ;
  16. const int INF = 99999999 ;
  17. const double esp = 1e-8 ;
  18. const long long mod= 1000 ;
  19. const int MX = 15 ;
  20. bool flag ;
  21. int g[MX][MX] ;
  22. bool row[MX][MX],col[MX][MX],vis[MX][MX] ;
  23. void dfs(int x,int y)
  24. {
  25. if(flag) return ;
  26. if(y==-1)
  27. {
  28. x-- ;
  29. y=8 ;
  30. }
  31. if(x==-1&&y==8)
  32. {
  33. for(int i=0 ;i<9 ;i++)
  34. {
  35. for(int j=0 ;j<9 ;j++)
  36. printf("%d",g[i][j]) ;
  37. printf("\n") ;
  38. }
  39. flag=true ;
  40. return ;
  41. }
  42. if(g[x][y])
  43. dfs(x,y-1) ;
  44. else
  45. {
  46. for(int i=1 ;i<=9 ;i++)
  47. if(!row[x][i]&&!col[y][i]&&!vis[3*(x/3)+y/3][i])
  48. {
  49. row[x][i]=true ;
  50. col[y][i]=true ;
  51. vis[3*(x/3)+y/3][i]=true ;
  52. g[x][y]=i ;
  53. dfs(x,y-1) ;
  54. g[x][y]=0 ;
  55. row[x][i]=false ;
  56. col[y][i]=false ;
  57. vis[3*(x/3)+y/3][i]=false ;
  58. }
  59. }
  60. }
  61. int main()
  62. {
  63. int Tx ;
  64. char s[MX] ;
  65. scanf("%d",&Tx) ;
  66. while(Tx--)
  67. {
  68. memset(row,false,sizeof(vis)) ;
  69. memset(col,false,sizeof(col)) ;
  70. memset(g,0,sizeof(g)) ;
  71. memset(vis,false,sizeof(vis)) ;
  72. int k,x ;
  73. for(int i=0 ;i<9 ;i++)
  74. {
  75. scanf("%s",s) ;
  76. for(int j=0 ;j<9 ;j++)
  77. {
  78. g[i][j]=x=s[j]-'0' ;
  79. if(x)
  80. {
  81. k=3*(i/3)+j/3 ;
  82. row[i][x]=true ;
  83. col[j][x]=true ;
  84. vis[k][x]=true ;
  85. }
  86. }
  87. }
  88. flag=false ;
  89. dfs(8,8) ;
  90. }
  91. return 0 ;
  92. }


 

文章来源: blog.csdn.net,作者:Linux猿,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/nyist_zxp/article/details/23018183

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

评论(0

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

全部回复

上滑加载中

设置昵称

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

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

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