题解 P1406 【方格填数】

· · 题解

这道题就是一道妥妥地暴(jian)力(zhi)搜索,

我们分析一下，这道题其实可以用搜索把一个个数填进去，每条横竖斜的和sum就等于a[1]+a[2]+……+a[n*n]除以n

即sum=(a[1]+a[2]+……+a[n*n])/n

这道题有一个易错点就是要字典序最小者输出，所以在搜索前要对a数组进行排序，我忘记了所以只拿了40分qwq

一开始用纯暴力搜索TLE了最后一个点 QAQ

纯暴力代码 预期得分 80分：

#include <bits/stdc++.h>
using namespace std;
const int N=20;
int n,a[N],ans[N][N],vst[N],sum;
bool isans(){//判断是否为正确的矩阵
    int cnt=0;
    //横向
    for(int i=1;i<=n;i++){
        cnt=0;
        for(int j=1;j<=n;j++) cnt+=ans[i][j];
        if(cnt!=sum) return 0; 
    }
    //竖向
    for(int j=1;j<=n;j++){
        cnt=0;
        for(int i=1;i<=n;i++) cnt+=ans[i][j];
        if(cnt!=sum) return 0;
    }
    //两个斜对角
    cnt=0;
    for(int i=1;i<=n;i++) cnt+=ans[i][i];   
    if(cnt!=sum) return 0;

    cnt=0;
    for(int i=1;i<=n;i++) cnt+=ans[i][n-i+1];
    if(cnt!=sum) return 0;

    return 1; 
}
void dfs(int x,int y){
    if(y==n+1) y=1,x++;//换行
    if(x==n+1){//结束之后判断
        if(isans()==1){
            for(int i=1;i<=n;i++,cout<<endl)
                for(int j=1;j<=n;j++)
                    cout<<ans[i][j]<<" ";
            exit(0);
        }
        else return;
    } 
    for(int i=1;i<=n*n;i++)//选择填哪个数
        if(!vst[i]){
            vst[i]=1; ans[x][y]=a[i];
            dfs(x,y+1);
            vst[i]=0; ans[x][y]=0;
        }
}
int main(){
    cin>>n;
    for(int i=1;i<=n*n;i++) cin>>a[i],sum+=a[i];
    sort(a+1,a+n*n+1);
    sum/=n;
    cout<<sum<<endl;
    dfs(1,1);
    return 0;
}

如果想要AC的话需要一个小小的剪枝：

我们一行一行填，填完一行就检查一下这一行的和是否等于sum，

如果不等于的话就不用搜索了。

剪枝搜索 预期得分 100分：

#include <bits/stdc++.h>
using namespace std;
const int N=20;
int n,a[N],ans[N][N],vst[N],sum;
bool isans(){
    int cnt=0;

    for(int i=1;i<=n;i++){
        cnt=0;
        for(int j=1;j<=n;j++) cnt+=ans[i][j];
        if(cnt!=sum) return 0; 
    }

    for(int j=1;j<=n;j++){
        cnt=0;
        for(int i=1;i<=n;i++) cnt+=ans[i][j];
        if(cnt!=sum) return 0;
    }

    cnt=0;
    for(int i=1;i<=n;i++) cnt+=ans[i][i];   
    if(cnt!=sum) return 0;

    cnt=0;
    for(int i=1;i<=n;i++) cnt+=ans[i][n-i+1];
    if(cnt!=sum) return 0;

    return 1; 
}
void dfs(int x,int y,int z){//z表示当前行的所有数之和
    if(y==n+1){
        y=1,x++;
        if(z!=sum) return;//剪枝
        z=0;
    } 
    if(x==n+1){
        if(isans()==1){
            for(int i=1;i<=n;i++,cout<<endl)
                for(int j=1;j<=n;j++)
                    cout<<ans[i][j]<<" ";
            exit(0);
        }
        else return;
    } 
    for(int i=1;i<=n*n;i++)
        if(!vst[i]){
            vst[i]=1; ans[x][y]=a[i];
            dfs(x,y+1,z+a[i]);
            vst[i]=0; ans[x][y]=0;
        }
}
int main(){
    cin>>n;
    for(int i=1;i<=n*n;i++) cin>>a[i],sum+=a[i];
    sort(a+1,a+n*n+1);
    sum/=n;
    cout<<sum<<endl;
    dfs(1,1,0);
    return 0;
}