P1406 40分 求助
  • 板块P1406 方格填数
  • 楼主hewo
  • 当前回复1
  • 已保存回复1
  • 发布时间2020/8/4 08:08
  • 上次更新2023/11/6 21:22:06
查看原帖
P1406 40分 求助
64976
hewo楼主2020/8/4 08:08

2个点出错一个TLE

#include<bits/stdc++.h>
//#include<windows.h>
using namespace std;
int m[100][100],a[100];
bool used[100];
int n,esum;//esum是综合 
int hang()
{
    int sum[10];
    for(int i=0;i<10;i++) sum[i]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            sum[i]+=m[i][j];
        }
    }
    for(int i=2;i<=n;i++)
    {
        if(sum[i]!=sum[i-1]) return 1e7-1;
    }
    return sum[1];//判断每一行的和是否一样,如果一样就返回值 
}
int lie()
{
    int sum[10];
    for(int i=0;i<10;i++) sum[i]=0;
    for(int j=1;j<=n;j++)
    {
        for(int i=1;i<=n;i++)
        {
            sum[j]+=m[i][j];
        }
    }
    for(int i=2;i<=n;i++)
    {
        if(sum[i]!=sum[i-1]) return 1e7;
    }
    return sum[1];//同理,判断列和 
}
int dj1()
{
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        sum+=m[i][i];
    }
    return sum;//对角线和(左上->右下) 
}
int dj2()
{
    int sum=0;
    for(int i=n,j=1;i>=1&&j<=n;i--,j++)
    {
        sum+=m[i][j];
    }
    return sum;//对角线和(右上->左上) 
}
void dfs(int x,int y,int num)
{
    if(x>=2&&y==1)
    {
        int sum=0;
        for(int i=1;i<=n;i++)
        {
            sum+=m[x-1][i];
        }
        if(sum*n!=esum) return ;//一个特判,如果上一行不是esum/n的话不可能正确,所以return 
    }
    if(num>n*n)
    {
        if(hang()==lie()&&hang()==dj1()&&hang()==dj2())//判断是否和相等 
        {
            cout<<hang()<<endl;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    cout<<m[i][j]<<" ";
                }
                cout<<endl;
            }
            //Sleep(10000);
            exit(0);//因为排过序,所以第一个一定最小,所以找到后直接结束 
        }
        else return ;   
    }
    else 
    {
        for(int i=1;i<=n*n;i++)
        {
            if(!used[i])
            {
                used[i]=1;
                m[x][y]=a[i];
                if(y<n)
                {
                    dfs(x,y+1,num+1);//从左往右1行1行来 
                    used[i]=0;
                }
                else
                {
                    dfs(x+1,1,num+1);
                    used[i]=0;
                }
            }
        }
    }
}
int main()
{
    //freopen("us1.out","w",stdout);因为有exit,所以用文件输出调试
    cin>>n;
    for(int i=1;i<=n*n;i++)
    {
        cin>>a[i];
        esum+=a[i];
    }
    sort(a+1,a+n+1);
    dfs(1,1,1);
    return 0;
}

2020/8/4 08:08
加载中...