蓝桥杯校内选拔赛/POJ 数独(深搜)
2024-08-30 10:09:00
Sudoku
Time Limit: 2000MS | Memory Limit: 65536K | |||
Total Submissions: 14530 | Accepted: 7178 | Special Judge |
Description
Sudoku is a very simple task. A square table with 9 rows and 9 columns is divided to 9 smaller squares 3x3 as shown on the Figure. In some of the cells are written decimal digits from 1 to 9. The other cells are empty. The goal is to fill the empty cells with decimal digits from 1 to 9, one digit per cell, in such way that in each row, in each column and in each marked 3x3 subsquare, all the digits from 1 to 9 to appear. Write a program to solve a given Sudoku-task.
Input
The input data will start with the number of the test cases. For each test case, 9 lines follow, corresponding to the rows of the table. On each line a string of exactly 9 decimal digits is given, corresponding to the cells in this line. If a cell is empty it is represented by 0.
Output
For each test case your program should print the solution in the same format as the input data. The empty cells have to be filled according to the rules. If solutions is not unique, then the program may print any one of them.
Sample Input
1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107
Sample Output
143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127
Source
搜索时要对行,列,每个小数独阵进行判断,判断该数字是否在这三个中出现过,是否出现用标识符标记,处理时i,j从下标0开始,处理行标,列标比较方便。思路较简单,看代码吧。
#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 12
using namespace std;
int num[MAXN][MAXN];
int row[MAXN][MAXN];//用来标记每一行九个数是否已被使用,使用记为1
int col[MAXN][MAXN];//列
int mar[MAXN][MAXN];//用0-8标识9个小数独矩阵
char chr[MAXN][MAXN];
bool flag=false;
void dfs(int m,int n)
{
int s,i,j; if(m==&&n==)
{
for(i=;i<=;i++)
{
for(j=;j<=;j++)
{
cout<<num[i][j];
}
cout<<endl;
}
flag=true;
}
else
{
if(num[m][n]!=)
{
if(n<=)
dfs(m,n+);
else
dfs(m+,);
}
else
{
for(i=;i<=;i++)
{
if(row[m][i]==&&col[n][i]==&&mar[m/*+n/][i]==)//根据i,j标定它所属的行,列,和所在的小矩阵
{
s=m/*+n/;
num[m][n]=i;
row[m][i]=;
col[n][i]=;
mar[s][i]=;
if(n<=)
dfs(m,n+);
else
dfs(m+,);
if(flag)
return ;
num[m][n]=;//一旦回溯过来,必须重新置0,因为说明此数字对于后面的搜索产生了不满足,故将其置0.
row[m][i]=;
col[n][i]=;
mar[s][i]=;
}
}
}
}
}
int main()
{
//freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
int i,j,s,t;
cin>>t;
while(t--)
{
memset(row,,sizeof(row));
memset(col,,sizeof(col));
memset(mar,,sizeof(mar));
for(i=;i<;i++)
scanf("%s",chr[i]);
for(i=;i<;i++)
for(j=;j<;j++)
{
num[i][j]=chr[i][j]-'';
s=num[i][j];
if(s!=)
{
row[i][s]=;
col[j][s]=;
mar[i/*+j/][s]=;//初始,一旦有数字,则要将它所在的行列及小矩阵标为1
}
}
flag=false;
dfs(,);
}
return ;
}
最新文章
- 模块化编程时,#include到底要放在哪里?
- Blend 2015 教程 (三) 模板
- CSU 1116 Kingdoms(枚举最小生成树)
- Java学习笔记(八)&mdash;&mdash;封装
- opensuse-13.1体验
- Linux系统之用户、群组和权限
- Java : 使用jar包里的图片作为窗体的ICON
- mysql实体关系(mysql学习五)
- [原博客] POJ 2975 Nim 统计必胜走法个数
- Vue学习之路---No.2(分享心得,欢迎批评指正)
- 尝试在条件“$(_DeviceSdkVersion) >= 21”中对计算结果为“”而不是数字的“$(_DeviceSdkVersion)
- MyBatis学习日记(二): MyBatis Say Hello
- 第九周博客作业<;西北师范大学|李晓婷>;
- php正则判断是否同时有数字和字母
- 01-BAT算法特训班
- C# 从类库中获取资源图片,把图片资源保存到类库中
- VC++ 报错:Heap corruption detected
- 玩转mongodb(二):mongodb基础知识
- 技术交流:DDD在企业开发的案例分享
- 170710、springboot编程之启动器Starter详解