深搜填数游戏
目录
深搜：填数游戏
关键词由CSDN通过智能技术生成
【题目描述】
这天Kendy路过KFC，看到KFC的橱窗上贴着大幅的宣传海报，海报上说，如果能在规定的时间内解决他们提出的问题，就可以获得价值100元的KFC最新款套餐。Kendy当然不想放过这样的机会。他发现题目是这样的：给你一个N×N的表格（3<N<10），在表格中事先已经填入了一部分的数字，现在请你的表格中空余的格子里填入1~N范围内的数字，使得整个表格的每一行和每一列都不存在重复的数字。 当然，为了保证公平，所有人拿到的表格都是随机的且标注了时间。这样Kendy就不可能把题目带回去慢慢研究了，因此他想请你帮忙以便在规定时间内能解决这个问题。 保证都有解。
样例输入
4 3 0 0 2 0 2 0 4 2 0 0 0 0 0 2 1
样例输出
3 1 4 2 1 2 3 4 2 4 1 3 4 3 2 1
这题的话我们把每个数都试一遍，如果这行和这列中没有这个数则进行下一个搜索。
【代码】
#include<bits/stdc++.h>
using namespace std;
int a[11][11],b[11][11];
int n;
bool checkx(int x) { //检查第几行
for(int i=1; i<=n; i++) {
if(b[x][i]==0)
continue;
for(int j=1; j<i; j++)
if(b[x][i]==b[x][j])
return false;
}
return true;
}
bool checky(int y) { //检查第几列
for(int i=1; i<=n; i++) {
if(b[i][y]==0)
continue;
for(int j=1; j<i; j++)
if(b[i][y]==b[j][y])
return false;
}
return true;
}
void dfs(int na,int nb) {//na:第几行，nb:第几列
if(na==n+1) {
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++)
printf("%d ",b[i][j]);
printf("\n");
}
exit(0);//本题只输出第一个解；如要输出全部解改为return;
}
if(b[na][nb]!=0) {
int nna=na,nnb=nb;
if(nb==n)
na++,nb=1;
else
nb++;
dfs(na,nb);
na=nna,nb=nnb;
return;
}
for(int i=1; i<=n; i++) {
b[na][nb]=i;
if(checkx(na)==false||checky(nb)==false) {//函数调用：判断这行和这列是否有重复
b[na][nb]=0;
continue;
}
int nna=na,nnb=nb;
if(nb==n)
na++,nb=1;
else
nb++;
dfs(na,nb);
na=nna,nb=nnb;
b[nna][nnb]=0;
}
}
int main() {
cin>>n;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
scanf("%d",&a[i][j]),b[i][j]=a[i][j];
dfs(1,1);
return 0;
}提交结果：
这个的话还可以优化一下：先建立一个数组c（值为false）用false表示可以填这个数，true表示不可以填这个数。然后检查这一行和这一列，如果这行或者这列有数已经填好了（假设为a[x][y]），那么将c[a[x][y]]=true（不能填这个数）。其他代码基本一样。
【代码】
#include<bits/stdc++.h>
using namespace std;
int a[11][11],b[11][11];
int n;
void dfs(int na,int nb) {
if(na==n+1) {
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++)
printf("%d ",b[i][j]);
printf("\n");
}
exit(0);//本题只输出第一个解；如要输出全部解改为return;
}
if(b[na][nb]!=0) {
int nna=na,nnb=nb;
if(nb==n)
na++,nb=1;
else
nb++;
dfs(na,nb);
na=nna,nb=nnb;
return;
}
bool c[11];//当前行能过够填什么数
memset(c,0,sizeof(c));
//检查这一行
for(int i=1; i<=n; i++) {
if(b[na][i]==0)
continue;
c[b[na][i]]=true;
}
//检查这一列
for(int i=1;i<=n;i++)
{
if(b[i][nb]==0)
continue;
c[b[i][nb]]=true;
}
for(int i=1; i<=n; i++) {
if(c[i]==true)
continue;
b[na][nb]=i;
int nna=na,nnb=nb;
if(nb==n)
na++,nb=1;
else
nb++;
dfs(na,nb);
na=nna,nb=nnb;
b[nna][nnb]=0;
}
}
int main() {
cin>>n;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
scanf("%d",&a[i][j]),b[i][j]=a[i][j];
dfs(1,1);
return 0;
}提交结果：
