HDU 5547 Sudoku(DFS)
题目网址:http://acm.hdu.edu.cn/showproblem.php?pid=5547
题目:
Sudoku
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 2372 Accepted Submission(s): 804
Actually, Yi Sima was playing it different. First of all, he tried to generate a 4×4 board with every row contains 1 to 4, every column contains 1 to 4. Also he made sure that if we cut the board into four 2×2 pieces, every piece contains 1 to 4.
Then, he removed several numbers from the board and gave it to another guy to recover it. As other counselors are not as smart as Yi Sima, Yi Sima always made sure that the board only has one way to recover.
Actually, you are seeing this because you've passed through to the Three-Kingdom Age. You can recover the board to make Yi Sima happy and be promoted. Go and do it!!!
It's guaranteed that there will be exactly one way to recover the board.
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
struct node{
int r,c;
};
vector<node>v;
char chess[][];
int col[][];//col[i][x]标记第i列 x数是否已经用过
int row[][];//row[i][x]标记第i行 x数是否已经用过
int block[][];//block[i][x]标记第i个分块,x数是否已经用过
int ok;
void dfs(int num){
if(ok) return ;
if(num==v.size()){//所有数都填好
for (int i=; i<; i++) {
puts(chess[i]);
}
ok=;
return ;
}
for(int i=;i<=;i++){
int r=v[num].r;
int c=v[num].c;
if(!col[c][i] && !row[r][i] && !block[r/*+c/][i]){
chess[r][c]=i+'';
col[c][i]=row[r][i]=;
block[r/*+c/][i]=;
dfs(num+);
col[c][i]=row[r][i]=;//回溯还原状态
block[r/*+c/][i]=;
chess[r][c]='*';
}
}
}
int main(){
int t;
scanf("%d",&t);
for (int i=; i<=t; i++) {
printf("Case #%d:\n",i);
v.clear();
memset(block, , sizeof(block));//初始值都为0,即都未用过
memset(col, , sizeof(col));
memset(row, , sizeof(row));
ok=;
for (int j=; j<; j++) {
scanf("%s",chess[j]);
for (int k=; k<; k++) {
if(chess[j][k]=='*'){//将需要填空的点放入vector容器
node x;
x.r=j;x.c=k;
v.push_back(x);
}else{
int x=chess[j][k]-'';//标记已经用过的点
block[j/*+k/][x]=;
row[j][x]=;
col[k][x]=;
}
}
}
dfs();//0表示在填空v[0]点
}
return ;
}
最新文章
- Delphi Webbrowser 修改 textarea 值 百度
- 看好你的门-客户端传数据-用java修改referer
- HTML5表单元素的学习
- Nodejs学习笔记(六)--- Node.js + Express 构建网站预备知识
- POJ 1552
- 系统级性能分析工具 — Perf
- Hibernate逍遥游记-第1章-JDBC访问数据库
- jQuery导航菜单防刷新
- linux之SQL语句简明教程---外部连接
- 初识Jmeter(一)
- 寻找Harris、Shi-Tomasi和亚像素角点
- 迈向c++的一次尝试
- LeetCode之“链表”:Intersection of Two Linked Lists
- 【转】分享JavaScript监听全部Ajax请求事件的方法
- Vue双向绑定原理,教你一步一步实现双向绑定
- 超详细的PDF Expert的注释功能介绍
- python之路--网络编程之socket
- windbg 定位崩溃问题
- iOS11 适配
- php读取文件内容几种正确方