和蓝桥杯以前一个题一样,但是数据加强了,博主水平有限,没做出来,先在这里记录一下,这里正解,下面是博主的超时做法。最近准备考研,不能深入学习了。

题目描述

数独是一种传统益智游戏,你需要把一个9 × 9的数独补充完整,使得图中每行、每列、每个3 × 3的九宫格内数字1~9均恰好出现一次。

请编写一个程序填写数独。

输入格式
输入包含多组测试用例。

每个测试用例占一行,包含81个字符,代表数独的81个格内数据(顺序总体由上到下,同行由左到右)。

每个字符都是一个数字(1-9)或一个”.”(表示尚未填充)。

您可以假设输入中的每个谜题都只有一个解决方案。

文件结尾处为包含单词“end”的单行,表示输入结束。

输出格式
每个测试用例,输出一行数据,代表填充完全后的数独。

样例

输入样例:
.2738..1..1...6735.......293.5692.8...........6.1745.364.......9518...7..8..6534.
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end
输出样例:
527389416819426735436751829375692184194538267268174593643217958951843672782965341
416837529982465371735129468571298643293746185864351297647913852359682714128574936
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int m[10][10],kx[10][10],ky[10][10],kk[10][10]; //kx:行 ky:列 kk:方格
int ans; void dfs(int x, int y) {
if (ans)return;
if (x == 9) {
ans = 1;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++)
cout << m[i][j];
}
cout << "\n";
}
if (m[x][y] == 0) {
for (int i = 1; i < 10; i++) {
if (kx[x][i]==0&&ky[y][i]==0&& kk[3 * (x / 3) + (y / 3)][i]==0) { kx[x][i] = 1;
ky[y][i] = 1;
kk[3 * (x/3) + (y/3)][i] = 1;
m[x][y] = i; if (y == 8)dfs(x + 1,0);
else dfs(x, y + 1); kx[x][i] = 0;
ky[y][i] = 0;
kk[3 * (x / 3) + (y / 3)][i] = 0;
m[x][y] = 0;
}
}
return;
}
else {
if (y == 8)dfs(x + 1, 1);
else dfs(x, y + 1);
}
} int main() {
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
string a;
while (cin >> a&&a[0] != 'e') {
memset(m, 0, sizeof(m));
memset(kx, 0, sizeof(kx));
memset(ky, 0, sizeof(ky));
memset(kk, 0, sizeof(kk));
ans = 0;
int len = a.size();
for (int i = 0; i < len; i++)
{
if (a[i] != '.') {
m[i / 9][i % 9] = a[i] - '0'; //终于把地图做好了。。
kx[i / 9][a[i] - '0'] = 1;
ky[i % 9][a[i] - '0'] = 1;
kk[3 * (i / 9 / 3) + (i % 9 / 3)][a[i] - '0'] = 1; //初始化
}
}
dfs(0, 0);
}
return 0;
}

  

 

最新文章

  1. 兼容IE8 input的placeholder的文字显示
  2. Redis修改数据多线程并发—Redis并发锁
  3. C# 自动生成代码API文档
  4. Jquery cxColor 示例演示
  5. 使用NodeList
  6. python time函数
  7. [ngRepeat:dupes] Duplicates in a repeater are not allowed. Use &#39;track by&#39; expression to specify uniq
  8. iOS之04-方法的声明和实现
  9. request实现页面包含
  10. Jenkins Code Sign error: No provisioning profiles found
  11. asp.net 捕获全局未处理异常的几种方法
  12. lintcode:Pow(x, n)
  13. Dll学习一_Dll 创建并动态引用窗体且释放窗体Demo
  14. Linux下MySQL的彻底卸载和安装配置字符集
  15. Lua: 给 Redis 用户的入门指导
  16. Head First 设计模式 第5章 单例模式
  17. win10 uwp 打开文件管理器选择文件
  18. Python系列之 - 锁(GIL,Lock,Rlock,Event,信号量)
  19. ionic3-ng4学习见闻--(自定义ion-tab图标)
  20. 如何使用JS来开发室内地图商场停车场车位管理系统

热门文章

  1. Extjs 环境安装【转】
  2. BufPay.com 个人收款接口 接入步骤
  3. cop2000实现补码两位乘
  4. 最优贸易(tarjan,spfa)
  5. MySQL索引的使用及注意事项
  6. 远程连接Oracle 服务器 解决Oracle查询中文乱码
  7. RHEL6(RedHat6)和SUSE11系统配置IPV6地址
  8. SpringBoot整合Swagger2以及生产环境的安全问题处理
  9. C语言实验报告(五) 两个正整数的最大公约数
  10. Docker开篇之基础概念篇