比赛 国庆欢乐赛3 评测结果 WTTTT
题目名称 不重叠正方形 最终得分 0
用户昵称 陆晨洗 运行时间 7.999 s
代码语言 C++ 内存使用 6.87 MiB
提交时间 2025-10-05 11:19:46
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
int a[1010][1010]={0};
bool b[1010][1010]={0};

void dfs3(int x,int y,int z)
{
    int i,j;
    for(i=x;i<=m;i++)
    {
        for(j=y;j<=m;j++)
        {
            if(b[i][j]==true)
            {
                return;
            }
            z=z+a[i][j];
        }
    }
    //cout<<ans<<" "<<z<<endl;
    ans=max(ans,z);
    return;
}
void dfs2(int x,int y,int z)
{
    int i,j;
    for(i=x;i<=m;i++)
    {
        for(j=y;j<=m;j++)
        {
            if(b[i][j]==true)
            {
                return;
            }
            z=z+a[i][j];
            b[i][j]=true;
        }
    }
    for(i=1;i<=n-m+1;i++)
    {
        for(j=1;j<=n-m+1;j++)
        {
            dfs3(i,j,z);
        }
    }
    for(i=x;i<=m;i++)
    {
        for(j=y;j<=m;j++)
        {
            b[i][j]=false;
        }
    }
    return;
}
void dfs1(int x,int y,int z)
{
    int i,j;
    for(i=x;i<=m;i++)
    {
        for(j=y;j<=m;j++)
        {
            z=z+a[i][j];
            b[i][j]=true;
        }
    }
            //cout<<z<<endl;
    for(i=1;i<=n-m+1;i++)
    {
        for(j=1;j<=n-m+1;j++)
        {
            dfs2(i,j,z);
        }
    }
    for(i=x;i<=m;i++)
    {
        for(j=y;j<=m;j++)
        {
            b[i][j]=false;
        }
    }
    return;
}
int main()
{
    freopen("zfx.in","r",stdin);
    freopen("zfx.out","w",stdout);
    int i,j;
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            cin>>a[i][j];
        }
    }
    for(i=1;i<=n-m+1;i++)
    {
        for(j=1;j<=n-m+1;j++)
        {
            dfs1(i,j,0);
        }
    }
    cout<<ans;
    return 0;
}