### 悬线法的具体实现

$f\left[i\right]\left[j\right]$表示以 $\left(i,j\right)$往左所能拓展的最大距离
$g\left[i\right]\left[j\right]$表示以 $\left(i,j\right)$往右所能拓展的最大距离
$w\left[i\right]\left[j\right]$表示以 $\left(i.j\right)$往上所能拓展的最大距离

if(满足条件){
w[i][j] = w[i-1][j] + 1;
f[i][j] = min(f[i][j], f[i-1][j]);
g[i][j] = min(g[i][j], g[i-1][j]);
}


### 以一道题作为例题吧（ZJOI2007棋盘制作）

#### 代码如下

#include <bits/stdc++.h>
#define N 2005
using namespace std;
int mp[N][N], f[N][N], g[N][N], w[N][N], ans1, ans2;
int main(){
int i, j, n, m, c;
scanf("%d%d", &n, &m);
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
scanf("%d", &mp[i][j]);
for(i = 1; i <= n; i++){
for(j = 1; j <= m; j++){
if(j > 1 && mp[i][j] != mp[i][j-1]) f[i][j] = f[i][j-1] + 1;
else f[i][j] = 1;
}
for(j = m; j >= 1; j--){
if(j < m && mp[i][j] != mp[i][j+1]) g[i][j] = g[i][j+1] + 1;
else g[i][j] = 1;
}
}
for(j = 1; j <= m; j++){
for(i = 1; i <= n; i++){
if(i > 1 && mp[i][j] != mp[i-1][j]){
w[i][j] = w[i-1][j] + 1;
f[i][j] = min(f[i][j], f[i-1][j]);
g[i][j] = min(g[i][j], g[i-1][j]);
}
else w[i][j] = 1;
}
}
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++){
c = min(w[i][j], f[i][j] + g[i][j] - 1);
ans1 = max(ans1, c * c);
ans2 = max(ans2, w[i][j] * (f[i][j] + g[i][j] - 1));
}
printf("%d\n%d", ans1, ans2);
return 0;
}


p4147玉蟾宫
p2701巨大的牛棚