首页 > 代码库 > 中山大学校队选拔赛第一章题4【简单数迷Simple Kakuro】-------2015年1月28日
中山大学校队选拔赛第一章题4【简单数迷Simple Kakuro】-------2015年1月28日
一：题意描述
本题就是给定一个迷宫，其中第一行和第一列都给定了数值。现在我们的任务就是需要把剩余的空格用1-9的数字把它填满，并且每行每列数值之和需要和行列标定的值相等。问最后是否可行，如果有多种方案需要输出一种方案。
二 ：题目分析
本题主要考查DFS当中剪枝技巧的利用以及DFS的方向规划问题。
首先我们可以根据题目已知信息得出行之和必须等于列之和。（第一次剪枝）
然后我们可以根据每一个数字不能在同一行或者同一列重复出现【设定标记】进行剪枝（第二次剪枝）
对于如果某一行（一列）数值还没有填满但是总和已经超过行列标定值之和，或者填满了但是总和和标定值不相等，那么我们必须剪枝。（第三次剪枝）
对于规划方向，我们可以采取从左到右从上到下的方式进行，当我们深搜把最后一个点深搜完毕时我们即可结束DFS，当然当sol（解决办法）>1时也可以结束递归。
三：AC代码
#include<iostream>#include<cstdio>#include<string.h>#include<math.h>#include<algorithm>using namespace std;#define maxn 300+10#define MOD 1000000000int sumrow[11],sumcol[11];//行列指定值之和int a[11][11],mark[11][11];//标记矩阵确定是否已经填上了数字int n,m;int curSumrow[11],curSumcol[11];//已经填上的行列值和int sol;int ans[11][11];int usedrow[11][10],usedcol[11][10];void Search(int x,int y){ if(sol>1) return;//说明有多种输出方案 if(x==n)//表明已经合乎要求 { sol++; for(int i=0;i<n;i++) for(int j=0;j<m;j++) ans[i][j]=a[i][j]; return; } int nx,ny; if(y==m-1) { nx=x+1; ny=0; } else { nx=x; ny=y+1; } if(mark[x][y]) { int ok=1; if(y<m-1&&curSumrow[x]>sumrow[x]||y==m-1&&curSumrow[x]!=sumrow[x]) ok=0; if(x<n-1&&curSumcol[y]>sumcol[y]||x==n-1&&curSumcol[y]!=sumcol[y]) ok=0; if(ok) Search(nx,ny); return; } for(int i=1;i<10;i++) if(!usedrow[x][i]&&!usedcol[y][i]) { usedcol[y][i]=1; usedrow[x][i]=1; curSumcol[y]+=i; curSumrow[x]+=i; a[x][y]=i; int go=1; if(y<m-1&&curSumrow[x]>sumrow[x]||y==m-1&&curSumrow[x]!=sumrow[x]) go=0; if(x<n-1&&curSumcol[y]>sumcol[y]||x==n-1&&curSumcol[y]!=sumcol[y]) go=0; if(go) Search(nx,ny); a[x][y]=0; usedcol[y][i]=0; usedrow[x][i]=0; curSumcol[y]-=i; curSumrow[x]-=i; }}int main(){ int T; int cas; int sumR,sumC; cin>>T; for(cas=1;cas<=T;cas++) { cin>>n>>m; sumC=sumR=0; int ok=1; memset(mark,0,sizeof(mark)); memset(usedcol,0,sizeof(usedcol)); memset(usedrow,0,sizeof(usedrow)); memset(curSumcol,0,sizeof(curSumcol)); memset(curSumrow,0,sizeof(curSumcol)); for(int i=0;i<n;i++) {cin>>sumrow[i];sumR+=sumrow[i];} for(int j=0;j<m;j++) {cin>>sumcol[j];sumC+=sumcol[j];} for(int i=0;i<n;i++) for(int j=0;j<m;j++) { cin>>a[i][j]; if(a[i][j]>0) { mark[i][j]=1; sumcol[j]+=a[i][j]; sumrow[i]+=a[i][j]; usedrow[i][a[i][j]]++; usedcol[j][a[i][j]]++; if(usedrow[i][a[i][j]]>1) ok=0; if(usedcol[j][a[i][j]]>1) ok=0; } }// for(int i=0;i<n;i++)// if(curSumrow[i]>sumrow[i]) ok=0;// for(int j=0;j<m;j++)// if(curSumcol[j]>sumcol[j]) ok=0; if(sumC!=sumR) ok=0; sol=0; cout<<ok<<endl; if(ok) Search(0,0); printf("Case %d:\n",cas); if(sol==0) cout<<"No answer."<<endl; else if(sol>1) cout<<"Not unique."<<endl; else{ for(int i=0;i<n;i++) { for(int j=0;j<m-1;j++) cout<<ans[i][j]<<‘ ‘; cout<<ans[i][m-1]<<endl; } } } return 0;}
四：总结
本题主要考察DFS的变式应用，以及对于设计DFS函数时剪枝技巧的利用。
中山大学校队选拔赛第一章题4【简单数迷Simple Kakuro】-------2015年1月28日
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。