Description
给定一个01矩阵，求出最大的正方形子矩阵和最大长方形子矩阵，并保证取出的矩阵中的元素都为0/1
Solution
为了使题目变成上述表述的形式，我们首先将读入的矩阵的部分元素xor1，使其变成一般形式
之后，这道题变成了两道题的合体：洛谷P2701巨大的牛棚与P4147玉蟾宫
我们分开讨论，对于最大正方形，我们设计一个dp，定义f[i][j]表示以(i, j)为右下角的最大正方形的边长，状态转移方程为
f[i][j] = min(f[i - 1][j - 1], f[i - 1][j], f[i][j - 1]) + 1
那么答案也是显然的，ans = max(f[i][j] * f[i][j])
对于最大矩形，我们使用单调栈求解，具体步骤请见
注意，本题要求求出最大正方形与矩形，所以我们要将这两个算法对0/1矩阵各做一遍，时间复杂度为O(n^2)
Code
1 #include2 #include 3 #include 4 using namespace std; 5 int n, m; 6 int a[2010][2010], vis[2010][2010]; 7 int ans1, f1[2010][2010], f2[2010][2010], ans2, b[2010]; 8 int s[2010], p, w[2010]; 9 int main() { 10 scanf("%d%d", &n, &m);11 for (register int i = 1; i <= m; ++i) vis[1][i] = vis[1][i - 1] ^ 1;12 for (register int i = 2; i <= n; ++i)13 for (register int j = 1; j <= m; j++)14 vis[i][j] = vis[i - 1][j] ^ 1;15 for (register int i = 1; i <= n; ++i)16 for (register int j = 1; j <= m; ++j) {17 scanf("%d", &a[i][j]);18 if(!vis[i][j]) a[i][j] ^= 1;19 }20 for (register int i = 1; i <= n; ++i)21 for (register int j = 1; j <= m; ++j)22 if (a[i][j]) {23 f1[i][j] = min(f1[i - 1][j - 1], min(f1[i - 1][j], f1[i][j - 1])) + 1;24 ans1 = max(ans1, f1[i][j]);25 }26 for (register int i = 1; i <= n; ++i)27 for (register int j = 1; j <= m; ++j)28 if (!a[i][j]) {29 f2[i][j] = min(f2[i - 1][j - 1], min(f2[i - 1][j], f2[i][j - 1])) + 1;30 ans1 = max(ans1, f2[i][j]);31 }32 printf("%d\n", ans1 * ans1);33 for (register int i = 1; i <= n; ++i) {34 for (register int j = 1; j <= m; ++j)35 b[j] = a[i][j] ? b[j] + 1 : 0;36 p = 0;37 for (register int j = 1; j <= m + 1; ++j) {38 if (b[j] > s[p]) s[++p] = b[j], w[p] = 1;39 else {40 int tot = 0;41 while (b[j] < s[p]) {42 tot += w[p];43 ans2 = max(ans2, s[p] * tot);44 p--;45 }46 s[++p] = b[j];47 w[p] = tot + 1;48 }49 }50 }51 for (register int i = 1; i <= n; ++i) {52 for (register int j = 1; j <= m; ++j)53 b[j] = a[i][j] == 0 ? b[j] + 1 : 0;54 p = 0;55 for (register int j = 1; j <= m + 1; ++j) {56 if (b[j] > s[p]) s[++p] = b[j], w[p] = 1;57 else {58 int tot = 0;59 while (b[j] < s[p]) {60 tot += w[p];61 ans2 = max(ans2, s[p] * tot);62 p--;63 }64 s[++p] = b[j];65 w[p] = tot + 1;66 }67 }68 }69 printf("%d\n", ans2);70 return 0;71 }