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:

Sample Output:

视频讲解：

POJ2676

解题代码：

#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);}
}