95pts 18 帮忙康康哪里有问题
查看原帖
95pts 18 帮忙康康哪里有问题
285328
Linnyx楼主2021/10/12 22:37
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m[1005][1005],flag[1005][1005],ans,anss,temp,temp2,k;
void dfs(int x,int y,int num,int node)
{
    if(x==1)
    {
        if(num+m[1][y]>ans)
        {
            ans=num+m[1][y];
            k=y;
        }
        return ;
    }
    if(y==n)node=2;
    if(y==1)node=4;
    if(x==n)node=3;
    if(node==1)
    {
        dfs(x+1,y+1,num+m[x][y],node);
    }
    else if(node==2)
    {
        dfs(x+1,y-1,num+m[x][y],node);
    }
    else if(node==3)
    {
        dfs(x-1,y-1,num+m[x][y],node);
    }
    else if(node==4)
    {
        dfs(x-1,y+1,num+m[x][y],node);
    }
}
void clean(int x,int y,int node)
{
    m[x][y]=0;
    if(x==1)return;
    if(y==n)node=2;
    if(y==1)node=4;
    if(x==n)node=3;
    if(node==1)
    {
        clean(x+1,y+1,node);
    }
    else if(node==2)
    {
        clean(x+1,y-1,node);
    }
    else if(node==3)
    {
        clean(x-1,y-1,node);
    }
    else if(node==4)
    {
        clean(x-1,y+1,node);
    }
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>m[i][j];
        }
    }
    for(int i=2;i<n;i++)
    {
        dfs(2,i+1,0,1);
    }
    for(int i=1;i<=n;i++)
    {
        temp2+=m[i][i];
        temp+=m[i][n-i+1];
    }
    ans=max({temp,temp2,ans});
    if(temp==ans)
    {
       for(int i=1;i<=n;i++)
        {
            m[i][n-i+1]=0;
        }
    }
    else if(temp2==ans)
    {
        for(int i=1;i<=n;i++)
        {
            m[i][i]=0;
        }
    }
    else
    clean(2,k+1,1);
    anss=ans;
    ans=0;temp=0;temp2=0;
    for(int i=2;i<n;i++)
    {
        dfs(2,i+1,0,1);
    }
    for(int i=1;i<=n;i++)
    {
        temp2+=m[i][i];
        temp+=m[i][n-i+1];
    }
    ans=max({ans,temp,temp2});
    cout<<anss+ans;
    return 0;
}

2021/10/12 22:37
加载中...