2015南阳CCPC H - Sudoku 暴力
H - Sudoku
Time Limit: 1 Sec
Memory Limit: 256 MB
题目连接
无
Description
Yi Sima was one of the best counselors of Cao Cao. He likes to play a funny game himself. It looks like the modern Sudoku, but smaller.
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!!!
Input
It's guaranteed that there will be exactly one way to recover the board.
Output
Sample Input
3 ****
2341
4123
3214 *243
*312
*421
*134 *41*
**3*
2*41
4*2*
Sample Output
Case #1:
1432
2341
4123
3214
Case #2:
1243
4312
3421
2134
Case #3:
3412
1234
2341
4123
HINT
题意
让你找到一个4*4的数独的合法解
题解:
直接爆搜就能过
代码:
#include<stdio.h>
#include<iostream>
#include<math.h>
using namespace std; string s[];
int p[][];
int tx[];
int ty[];
int tot = ;
int flag;
int vis[];
int check()
{
for(int i=;i<;i++)
{
vis[]=vis[]=vis[]=vis[]=;
for(int j=;j<;j++)
{
if(p[i][j]==)continue;
if(vis[p[i][j]])return ;
vis[p[i][j]]=;
}
}
for(int j=;j<;j++)
{
vis[]=vis[]=vis[]=vis[]=;
for(int i=;i<;i++)
{
if(p[i][j]==)continue;
if(vis[p[i][j]])return ;
vis[p[i][j]]=;
}
}
vis[]=vis[]=vis[]=vis[]=;
for(int i=;i<;i++)
{
for(int j=;j<;j++)
{
if(p[i][j]==)continue;
if(vis[p[i][j]])return ;
vis[p[i][j]]=;
}
} vis[]=vis[]=vis[]=vis[]=;
for(int i=;i<;i++)
{
for(int j=;j<;j++)
{
if(p[i][j]==)continue;
if(vis[p[i][j]])return ;
vis[p[i][j]]=;
}
}
vis[]=vis[]=vis[]=vis[]=;
for(int i=;i<;i++)
{
for(int j=;j<;j++)
{
if(p[i][j]==)continue;
if(vis[p[i][j]])return ;
vis[p[i][j]]=;
}
}
vis[]=vis[]=vis[]=vis[]=;
for(int i=;i<;i++)
{
for(int j=;j<;j++)
{
if(p[i][j]==)continue;
if(vis[p[i][j]])return ;
vis[p[i][j]]=;
}
}
return ;
}
void dfs(int x)
{
if(flag)return;
if(x==tot){
for(int i=;i<;i++)
{
for(int j=;j<;j++)
printf("%d",p[i][j]);
printf("\n");
}
flag=;
return;}
for(int i=;i<=;i++)
{
p[tx[x]][ty[x]]=i;
if(check())
dfs(x+);
p[tx[x]][ty[x]]=;
}
}
int main()
{
int t;scanf("%d",&t);
for(int cas = ;cas <= t;cas++)
{
tot = ;
flag = ;
for(int i=;i<;i++)
cin>>s[i];
for(int i=;i<;i++)
for(int j=;j<;j++)
if(s[i][j]=='*')
p[i][j]=;
else
p[i][j]=s[i][j]-''; for(int i=;i<;i++)
for(int j=;j<;j++)
if(p[i][j]==)
{
tx[tot]=i;
ty[tot]=j;
tot++;
}
printf("Case #%d:\n",cas);
dfs();
}
}
最新文章
- Mysql错误:Ignoring query to other database解决方法
- 《Effective Java》—— 对于所有对象都通用的方法
- Qt5 发布的exe应用程序Windows下无法执行的问题解决方案
- mysql 同步
- ASP.NET MVC中使用highcharts 生成简单的折线图
- CentOS 6.5部署安装Memcached
- 《Linux内核设计与实现》课程学习重点问题总结
- Android ScrollView 嵌套 ListView、 ListView 嵌套ScrollView Scroll事件冲突解决办法
- javascript如何自动去除所有空格?
- Linux下实现秒级定时任务的两种方案(crontab 每秒运行)
- Linux网络设置(第二版) --Linux网络设置
- springboot之scheduled任务调度
- win10 + gtx1060 + cuda8.0 + caffe + vs2013 + Tensorflow + PyTorch
- TLS 改变密码标准协议(Change Cipher Spec Protocol) 就是加密传输中每隔一段时间必须改变其加解密参数的协议
- 在AbpZero中hangfire后台作业的使用——hangfire的调度
- idea 配置简单web
- android framework-下载Android系统源代码
- 如果我们的MCU调试不通过,我们该如何测试?(未完待续)
- Gridview数据导出excel时身份证号码为科学计数法的解决方法
- python模块之XlsxWriter 详解