POJ2676题解（dfs，附：视频讲解）

本文主要是介绍POJ2676题解（dfs，附：视频讲解），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

Time Limit:	Memory Limit:
2000MS	65536K

• Description：
  数独是一项非常简单的任务。一个有9行9列的正方形表格被分成9个较小的正方形3x3，如图所示。在某些单元格中，是从1到9的十进制数字。其他单元格是空的。目标是用1到9的十进制数字填充空单元格，每个单元格一个数字，这样在每行、每列和每个标记的3x3子方格中，1到9的所有数字都会出现。写一个程序来解决给定的数独任务。
  
• Input:
  输入数据将从测试用例的数量开始。 对于每个测试用例，紧跟着表的行的是9行。 在每一行上，给出了一个准确的9位十进制数字的字符串，对应于该行中的单元格。 如果单元格为空，则用0表示。
• Output:
  对于每个测试用例，您的程序应以与输入数据相同的格式打印解决方案。 空单元格必须根据规则进行填充。 如果解决方案不是唯一的，则程序可以打印其中任何一种。
• Sample Input:

1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

• Sample Output:

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

视频讲解：

解题代码：

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
int map[9][9] = { 0 };
int flag = 0;
void dfs(int i, int j)
{   if (flag)return;if (j > 8){i++;j = 0;if (i > 8){flag = 1;for (int m = 0; m < 9; m++){for (int n = 0; n < 9; n++){cout << map[m][n];}cout << endl;}return;}}if (map[i][j] == 0){   int f[10] = { 0,0 };for (int k = 0; k < 9; k++)f[map[i][k]]++;for (int k = 0; k < 9; k++)f[map[k][j]]++;for (int k = i / 3 * 3; k < i / 3 * 3 + 3; k++)for (int l = j / 3 * 3; l < j / 3 * 3 + 3; l++)f[map[k][l]]++;for (int k = 1; k < 10; k++)if (f[k] == 0){   map[i][j] = k;dfs(i, j + 1);map[i][j] = 0;}}else {dfs(i, j + 1);}return;
}
int main()
{int c;cin >> c;char ch;for (int i = 0; i < c; i++){   flag = 0;for (int m = 0; m < 9; m++)for (int n = 0; n < 9; n++){   cin >> ch;map[m][n]=ch-'0';}dfs(0, 0);}
}

这篇关于POJ2676题解（dfs，附：视频讲解）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---