传送门：点击打开链接
题意：求全红的矩形，或者全蓝的矩形，或者红蓝相间的矩形，这些矩形中周长的最大值
思路：大白书上有方法解释了如何利用动态规划思想去做求最大子矩阵，这里就不多说了。求最大子矩阵还有另外一种方法，就是利用单调栈，这也是一种非常棒的方法。这题还有一个小技巧，就是如何处理红蓝相间的呢。。我们直接把(i+j)%2==1的全部翻转，这样再做一次求最大子矩阵，，就搞定了
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck printf("fuck")
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;const int MX = 1000 + 5;int n, m;
char G[MX][MX];
int S[MX][MX];int preL[2][MX], preR[2][MX];
int L[2][MX][MX], R[2][MX][MX], H[2][MX][MX];int solve() {int ret = 0;for(int i = 1; i <= n; i++) {preL[0][0] = preL[1][0] = 0;for(int j = 1; j <= m; j++) {preL[0][j] = S[i][j] == 1 ? j : preL[0][j - 1];preL[1][j] = S[i][j] == 0 ? j : preL[1][j - 1];}preR[0][m + 1] = preR[1][m + 1] = m + 1;for(int j = m; j >= 1; j--) {preR[0][j] = S[i][j] == 1 ? j : preR[0][j + 1];preR[1][j] = S[i][j] == 0 ? j : preR[1][j + 1];}for(int j = 1; j <= m; j++) {if(S[i][j] == 0) {if(i == 1 || S[i - 1][j] == 1) {L[0][i][j] = preL[0][j];R[0][i][j] = preR[0][j];H[0][i][j] = 1;} else {H[0][i][j] = H[0][i - 1][j] + 1;L[0][i][j] = max(L[0][i - 1][j], preL[0][j]);R[0][i][j] = min(R[0][i - 1][j], preR[0][j]);}int w = R[0][i][j] - L[0][i][j] - 1, h = H[0][i][j];ret = max(ret, 2 * w + 2 * h);}if(S[i][j] == 1) {if(i == 1 || S[i - 1][j] == 0) {L[1][i][j] = preL[1][j];R[1][i][j] = preR[1][j];H[1][i][j] = 1;} else {H[1][i][j] = H[1][i - 1][j] + 1;L[1][i][j] = max(L[1][i - 1][j], preL[1][j]);R[1][i][j] = min(R[1][i - 1][j], preR[1][j]);}int w = R[1][i][j] - L[1][i][j] - 1, h = H[1][i][j];ret = max(ret, 2 * w + 2 * h);}}}return ret;
}int main() {int T, ansk = 0; //FIN;scanf("%d", &T);while(T--) {scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) {scanf("%s", G[i] + 1);for(int j = 1; j <= m; j++) {S[i][j] = G[i][j] == 'B' ? 1 : 0;}}int ans = solve();for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {S[i][j] = G[i][j] == 'B' ? 1 : 0;if((i + j) % 2 == 1) S[i][j] ^= 1;}}ans = max(ans, solve());printf("Case #%d: %d\n", ++ansk, ans);}return 0;
}