求助,除1号点外其余答案都少了1,类贪心尺取法

P1736 创意吃鱼法

EastIsRed @ 2023-07-25 20:34:32

#include<cstdio>
using namespace std;
int n,m;
int mp[2560][2560],preh[2560][2560],prew[2560][2560];
int mark[2560][2560];
inline bool check1(int x1,int y1,int x2,int y2)//i+l,j+l,i+temp,j+temp;
{
    return preh[x2][y2-1]-preh[x2][y1-1]+prew[x2-1][y2]-prew[x1-1][y2]==0;
}
inline bool check2(int x1,int y1,int x2,int y2)//i+l,j-l,i+temp,j-temp;
{
    return preh[x2][y1]-preh[x2][y2]+prew[x2-1][y2]-prew[x1-1][y2]==0;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&mp[i][j]);
            preh[i][j]=preh[i][j-1]+mp[i][j];
            prew[i][j]=prew[i-1][j]+mp[i][j];
        }
    int mx=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(mp[i][j]&&!mark[i][j])
            {
                int l=0,r=1;
                mark[i][j]=1;
                while(i+r<=n&&j+r<=m)
                {
                    while(i+r<=n&&j+r<=m&&mp[i+r][j+r]&&check1(i+l,j+l,i+r,j+r))
                    {
                        if(mx<r-l)
                            mx=r-l;
                        mark[i+r][j+r]=1,r++;
                    }
                    if(i+r>n||j+r>m||!mp[i+r][j+r])
                        break;
                    while(l<r&&!check1(i+l,j+l,i+r,j+r))
                        l++;
                }
            }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(mp[i][j]&&mark[i][j]<=1)
            {
                int l=0,r=1;
                mark[i][j]=2;
                while(i+r<=n&&j-r>0)
                {
                    while(i+r<=n&&j-r>0&&mp[i+r][j-r]&&check2(i+l,j-l,i+r,j-r))
                    {
                        if(mx<r-l)
                            mx=r-l;
                        mark[i+r][j-r]=2,r++;
                    }
                    if(i+r>n||j-r<=0||!mp[i+r][j-r])
                        break;
                    while(l<r&&!check2(i+l,j-l,i+r,j-r))
                        l++;
                }
            }
    printf("%d",mx);
    return 0;
}

by EastIsRed @ 2023-07-25 20:58:37

楼主自查,

if(mx<r-l)
   mx=r-l;

此段更新中的r-l应改为r-l+1

我是傻*


|