赞
踩
输入9行,每行为空格隔开的9个数字,为0的地方就是需要填充的。
输出九行,每行九个空格隔开的数字,为解出的答案。
思路:深搜+剪枝 == 递归+回溯
凡是类似于迷宫的寻找路径的问题,均可由“递归+回溯”。
本题中,从第一个为0处开始填值,从1-9依次往里填i,如果当前填的值i深搜的结果为false,则把其状态还原(回溯),然后继续填下个值i+1。依次递归下去,当一直找到(9,9)时,即成功。
特别注意:每行不能多输出个空格,即使看不见,也不能多输出一个空格。
- #include <iostream>
- #include <iomanip>
- #include <cstring>
- using namespace std;
- #define N 10
- int hashrow[N][N];
- int hashcol[N][N];
- int hashblock[N][N];
- int array[N][N];
-
-
- bool dfs(int i,int j){
- while(array[i][j]!=0){
- if(i==9&&j==9){
- return true;
- }else if(j==9){
- i++;
- j=1;
- }
- else
- j++;
- }
-
- for (int k = 1; k <=9 ; ++k)
- {
- if(hashrow[i][k]==0&&hashcol[j][k]==0&&hashblock[(i-1)/3*3+(j-1)/3+1][k]==0){
- array[i][j]=k;
- hashrow[i][k]=1;
- hashcol[j][k]=1;
- hashblock[(i-1)/3*3+(j-1)/3+1][k]=1;
- if(dfs(i,j)==true)
- return true;
- array[i][j]=0; //深搜+剪枝 回溯法
- hashrow[i][k]=0;
- hashcol[j][k]=0;
- hashblock[(i-1)/3*3+(j-1)/3+1][k]=0;
- }
- }
- return false;//填当前空格时,从1到9,没有一个能成功,则返回.
-
- }
-
-
-
- int main()
- {
- memset(hashrow,0,sizeof(hashrow));
- memset(hashcol,0,sizeof(hashcol));
- memset(hashblock,0,sizeof(hashblock));
-
- for (int i = 1; i <= 9; ++i)
- {
- for (int j = 1; j <= 9; ++j)
- {
- cin>>array[i][j];
- hashrow[i][array[i][j]]=1;//
- hashcol[j][array[i][j]]=1;
- hashblock[(i-1)/3*3+(j-1)/3+1][array[i][j]]=1;
- }
- }
- if(dfs(1,1))
- {
- for (int i = 1; i <= 9; ++i)
- {
- for (int j = 1; j <= 8; ++j)
- {
- cout<<array[i][j]<<" ";//每行的最后不能多输出一个空格。
- }
- cout<<array[i][9]<<endl;//最后不能多输出一个空格。
- }
- }
-
-
- return 0;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。