很久没见这类有趣的问题了。让我想起了以前小曹发过的瓷砖问题。

在看别人的答案之前，我习惯先自己解决（思考，不正是玩ACM的乐趣么），晚一点和大家交流。

最近工作比较忙，不能天天来论坛玩，各位朋友见谅。

境界不够丶继续修炼

自己顶下

楼主是高人嘛    可不可以说说想法？

求教贴。。
我也不会额

太BTle

虚心求教

好吧，今天晚上写一篇详细的解析

小曹过了吗？
有点郁闷，所有能想到的数据都测试过了，讨论区的数据也测试了一遍，但提交就是WA，呵呵。
不太爽，先把这段WA代码放上来给大家点评吧。

#include<stdio.h>
int ls[60];
int lc[60];
char lm[60][60];

int is_right(int s)
{
    for(; s; s >>= 1)
    if(s & 1 && s & 6) return 0;
    return 1;
}

int count(int s)
{
    int c;
    for(c = 0; s; c++) s &= s - 1;
    return c;
}

void initial()
{
    int i, j;
    for(j = i = 0; i < 586; i++)
        if(is_right(i)) lc[j] = count(ls[j] = i), j++;
    for(lm[0][0] = 1, i = 0; i < 60; i++)
    for(j = i + 1; j < 60; j++) lm[i][j] = lm[j][i] = (ls[i] & ls[j]) == 0;
}

int cal(int *map, int n, int m)
{
    int a[2][60][60] = {0}, (*f)[60] = a[0], (*p)[60] = a[1], (*t)[60];
    int w, i, j, k, r, c;
    for(w = 1 << m, i = 59; i > 0 && ls[i] >= w; i--); w = i;
    for(i = 0; i < n; i++, t = p, p = f, f = t)
    {
        for(j = 0; j <= w; j++)
        {
            if(ls[j] & map[i])
            {
                for(k = 0; k <= w; p[j][k++] = -1);
                continue;
            }
            for(k = 0; k <= w; p[j][k++] = c)
            {
                if(!lm[j][k]){ p[j][k] = -1; continue; }
                for(c = -1, r = 0; r <= w; r++)
                if(f[k][r] >= 0 && lm[j][r] && f[k][r] + lc[j] > c) c = f[k][r] + lc[j];
            }
        }
    }
    for(c = i = 0; i <= w; i++)
    for(j = 0; j <= w; j++)
    if(f[i][j] > c) c = f[i][j];
    return c;
}

int main()
{
    char str[32];
    int map[256], n, m, i, j;
    initial();
    scanf("%d%d", &n, &m);
    for(i = 0; i < n; i++)
    {
        scanf("%s", str);
        map[i] = 0;
        for(j = 0; j < m; j++)
            map[i] = (map[i] << 1) + (str[j] == 'H');
    }
    printf("%d\n", cal(map, n, m));
    return 0;
}

这种帖子确实好，理论用于实际，顶起