搜索——洛谷 P1406 方格填数

最初一股脑暴力，发现超时，于是开始优化。
最后的S其实就是所有数的和除以n。
没必要都填完再判断，填一行判断一行；填到最后一行时，填一列判断一列；填到最后一个数时判断对角线是否符合即可。

#include
using namespace std;
#define ll long long
int a[20],vis[20],mp[5][5],f,n;
ll aver;
bool ok(int x,int y){
    ll sum=0;
    if(y==n){
        for(int i=1;i<=n;i++)sum+=mp[x][i];
        if(sum!=aver)return 0;
    }
    sum=0;
    if(x==n){
        for(int i=1;i<=n;i++)sum+=mp[i][y];
        if(sum!=aver)return 0;
    }

    if(x==n&&y==n){
        sum=0;
        for(int i=1;i<=n;i++)sum+=mp[i][i];
        if(sum!=aver)return 0;
        sum=0;
        for(int i=1;i<=n;i++)sum+=mp[i][n+1-i];
        if(sum!=aver)return 0;
    }
    return 1;
}

void dfs(int x,int y,int cnt){
    if(f||!ok(x,y))return;
    

    if(x==n&&y==n){
        f=1;
        cout<n)x++,y=1;

    for(int i=1;i<=n*n;i++){
        if(!vis[i]){
            vis[i]=1;
            mp[x][y]=a[i];
            dfs(x,y,cnt+1);
            vis[i]=0;
            mp[x][y]=0;
        }
    }


}

int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n*n;i++){
        cin>>a[i];
        aver+=a[i];
    }
    aver/=n;
    sort(a+1,a+1+n*n);
    for(int i=1;i<=n*n;i++){
        //cout<