hdu 4328 Cut the cake

悬线法。求解子矩阵的最大周长。子矩阵可以是单色的，也可以是两种颜色交错的。因为题目矩阵范围是1000，所以明显是悬线法。。。注意：考虑好把方格当做点和普通点的区别。给几组数据做测试用吧。。。

#include<algorithm>  
#include<iostream>  
#include<cstring>  
#include<cstdio>  
#include<cmath>  
#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

补充：软件开发 , C++ ,