[HOJ] 54 青蛙子

從邊邊隨便跳

複雜度不知道

#include<cstdio>
#define MAX 5005
int max(int a,int b){
    return a>b? a:b;
}
bool map[MAX][MAX],f;
int r[MAX],c[MAX],n,dr,dc,rn,cn,nr,nc,cnt,ans;
int main(){
    scanf("%d%d%d",&rn,&cn,&n);
    for(int i=0;i<n;i++){
        scanf("%d%d",&r[i],&c[i]);
        map[r[i]][c[i]]=true;
    }
         
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j)continue;
            dr=r[j]-r[i];
            dc=c[j]-c[i];
            if((r[i]-dr>0&&r[i]-dr<=rn)&&(c[i]-dc>0&&c[i]-dc<=cn))
                continue;
            f=false;
            cnt=2;
            nr=r[j]+dr;
            nc=c[j]+dc;
            while(1){
                if(nr<1||nr>rn||nc<1||nc>cn){
                    f=true;
                    break;
                }
                if(!map[nr][nc])break;
                cnt++;
                nr+=dr;
                nc+=dc;
            }
            if(f)ans=max(ans,cnt);
        }
    }
    if(ans>2)printf("%d\n",ans);
    else puts("0");
}