题目大意
给定一个 n×m 的黑白网格,在其上找一个面积最大的正方形、矩形的黑白相间的网格,输出最大面积。
1⩽n,m⩽2,000
题目链接
【ZJOI 2007】棋盘制作 - Luogu 1169
题解
悬线法。
对每个格子 (i,j) ,求出 up(i,j) 、left(i,j) 、right(i,j) 分别表示从该格子向上最远能取多远、以及在取这么远的情况下能向左/右拓展到的最远位置。
up(i,j)={1i=1or(i,j)=(i−1,j)up(i−1,j)+1(i,j)=(i−1,j)left(i,j)={loi=1or(i,j)=(i−1,j)max(left(i−1,j),lo)(i,j)=(i−1,j)right(i,j)={roi=1or(i,j)=(i−1,j)max(right(i−1,j),ro)(i,j)=(i−1,j)
其中,lo 每行从左开始计算,表示当前格向左最远能到的位置,ro 与之相反。
扫一遍网格即可求出以上三个数组。此时,对于每个格子 (i,j) ,up(i,j)×(right(i,j)−left(i,j)+1) 表示该点能扩展出的最大的黑白相间的矩形。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
| #include <cstdio> #include <algorithm> const int MAXN = 2005; int main() { int n, m; scanf("%d %d", &n, &m); static int mat[MAXN][MAXN], up[MAXN][MAXN], left[MAXN][MAXN], right[MAXN][MAXN]; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { scanf("%d", &mat[i][j]); if (i == 1 || mat[i][j] == mat[i - 1][j]) up[i][j] = 1; else up[i][j] = up[i - 1][j] + 1; } for (int i = 1; i <= n; i++) { int lo = 1; for (int j = 1; j <= m; j++) { if (j == 1) { left[i][j] = 1; continue; } if (mat[i][j] == mat[i][j - 1]) lo = j; left[i][j] = lo; if (up[i][j] > 1) left[i][j] = std::max(left[i - 1][j], lo); } } for (int i = 1; i <= n; i++) { int ro = m; for (int j = m; j; j--) { if (j == m) { right[i][j] = m; continue; } if (mat[i][j] == mat[i][j + 1]) ro = j; right[i][j] = ro; if (up[i][j] > 1) right[i][j] = std::min(right[i - 1][j], ro); } } int ansSqr = 0, ansRect = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { int bottom = right[i][j] - left[i][j] + 1; int height = up[i][j]; ansRect = std::max(ansRect, bottom * height); ansSqr = std::max(ansSqr, std::min(bottom, height) * std::min(bottom, height)); } printf("%d\n%d\n", ansSqr, ansRect); return 0; }
|