悬线法。求解子矩阵的最大周长。子矩阵可以是单色的，也可以是两种颜色交错的。因为题目矩阵范围是1000，所以明显是悬线法。。。注意：考虑好把方格当做点和普通点的区别。给几组数据做测试用吧。。。
#include
#include
#include
#include
#include
#define LL long long
#define CLR(a, b) memset(a, b, sizeof(a))
using namespace std;
const int N = 1010;
char G[N][N];
int L[N][N], R[N][N], H[N][N];
int l[N][N], r[N][N], n, m, ans;
void Solve(char C)
{
int tmp;
for(int i = 0; i < n; i ++)
{
tmp = -1;
for(int j = 0; j < m; j ++)
{
if(G[i][j] == C) tmp = j;
l[i][j] = tmp;
}tmp = m;
for(int j = m - 1; j >= 0; j --)
{
if(G[i][j] == C) tmp = j;
r[i][j] = tmp;
}
}
for(int j = 0; j < m; j ++)
{
if(G[0][j] == C) H[0][j] = 0;
else H[0][j] = 1;
L[0][j] = l[0][j];
R[0][j] = r[0][j];
}
for(int i = 1; i < n; i ++)
for(int j = 0; j < m; j ++)
{
if(G[i - 1][j] == C)
{
H[i][j] = 1;
L[i][j] = l[i][j];
R[i][j] = r[i][j];
}
else
{
H[i][j] = H[i - 1][j] + 1;
L[i][j] = max(l[i][j], L[i - 1][j]);
R[i][j] = min(r[i][j], R[i - 1][j]);
}
}
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < m; j ++)
{
if(R[i][j] - L[i][j] - 1 > 0) ans = max(ans, H[i][j] + (R[i][j] - L[i][j] - 1));
}
}
}
void Solve2()
{
int tmp;
for(int i = 0; i < n; i ++)
{
l[i][0] = 0;tmp = 0;
for(int j = 1; j < m; j ++)
{
if(G[i][j] == G[i][j - 1]) tmp = j;
l[i][j] = tmp;
}
r[i][m - 1] = tmp = m - 1;
for(int j = m - 2; j >
= 0; j --)
{
if(G[i][j] == G[i][j + 1]) tmp = j;
r[i][j] = tmp;
}
}
for(int j = 0; j < m; j ++)
{
H[0][j] = 1;
L[0][j] = l[0][j];
R[0][j] = r[0][j];
}
for(int i = 1; i < n; i ++)
for(int j = 0; j < m; j ++)
{
if(G[i][j] == G[i - 1][j])
{
H[i][j] = 1;
L[i][j] = l[i][j];
R[i][j] = r[i][j];
}
else
{
H[i][j] = H[i - 1][j] + 1;
L[i][j] = max(l[i][j], L[i - 1][j]);
R[i][j] = min(r[i][j], R[i - 1][j]);
}
}
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < m; j ++)
{
ans = max(ans, H[i][j] + (R[i][j] - L[i][j] + 1));
}
}
}
int main()
{
//freopen("in.txt", "r", stdin);
int t, cas = 1;
scanf("%d", &t);
while(t --)
{
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i ++)
{
scanf("%s", G[i]);
}ans = 0;
Solve('R');Solve('B');
Solve2();
printf("Case #%d: %d\n", cas ++, 2 * ans);
}
}
10
7 4
BBRB
RBRB
RRRR
RRRB
RRBB
BRBB
RBRB
4 1
B
R
B
R
4 3
BBR
BRB
BBR
RRB
3 1
R
B
B
5 4
RRBR
BRRB
RRRB
RBRR
RBBR
3 10
BRBRRBRRBB
RRBRRBRRRB
RBBBRRRRRB
5 3
RBR
RBR
RBB
RBR
RBR
6 4
RBBR
BBBB
RBRR
BRRR
BRRB
RBRR
1 8
RBBBBRRB
2 1
B
B
Case #1: 10
Case #2: 10
Case #3: 12
Case #4: 6
Case #5: 8
Case #6: 12
Case #7: 12
Case #8: 10
Case #9: 10
Case #10: 6