悬线法 || BZOJ 1057: [ZJOI2007]棋盘制作 || Luogu P1169 [ZJOI2007]棋盘制作

题面：P1169 [ZJOI2007]棋盘制作

题解：

基本是悬线法板子，只是建图判断时有一点点不同。

代码：

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #define min(a,b) ((a)<(b)?(a):(b))

 #define max(a,b) ((a)>(b)?(a):(b))

 using namespace std;

 inline int rd(){

     int x=,f=;char c=getchar();

     while(c<''||c>''){if(c=='-')f=-; c=getchar();}

     while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

     return f*x;

 }

 const int maxn=,maxm=maxn;

 int N,M,C[maxn][maxm],H[maxn][maxm],L[maxn][maxm],R[maxn][maxm],ans1=,ans2=,w;

 int main(){

     N=rd();M=rd();

     for(int i=;i<=N;i++)

         for(int j=;j<=M;j++)

             C[i][j]=rd();

     for(int i=;i<=N;i++)

         for(int j=;j<=M;j++){

             if(i==||C[i][j]!=C[i-][j])

                 H[i][j]=H[i-][j]+;

             else H[i][j]=;//H

             if(j==||C[i][j]!=C[i][j-])

                 L[i][j]=L[i][j-]+;

             else L[i][j]=;//L

             int r=M-j+;

             if(j==||C[i][r]!=C[i][r+])

                 R[i][r]=R[i][r+]+;

             else R[i][r]=;

         }

     for(int i=;i<=N;i++)

         for(int j=;j<=M;j++){

             if(H[i][j]>){

                 L[i][j]=min(L[i][j],L[i-][j]);

                 R[i][j]=min(R[i][j],R[i-][j]);

             }

             w=L[i][j]+R[i][j]-;

             ans1=max(ans1,min(w,H[i][j])*min(w,H[i][j]));

             ans2=max(ans2,w*H[i][j]);

         }

     printf("%d\n%d\n",ans1,ans2);

     return ;

 }

---

By:AlenaNuna