POJ1185:火炮(减少国家)

Description

命令将军打算N*M该网络格他们的炮兵部队部署在地图上。一个N*M该地图由N行M列，每个地图格它可以是山（使用"H" 表示），也可能是平原（用"P"表示），例如以下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不可以部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所看到的：

假设在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它可以攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其他白色网格均攻击不到。

从图上可见炮兵的攻击范围不受地形的影响。
如今，将军们规划怎样部署炮兵部队，在防止误伤的前提下（保证不论什么两支炮兵部队之间不能互相攻击，即不论什么一支炮兵部队都不在其它支炮兵部队的攻击范围内），在整个地图区域内最多可以摆放多少我军的炮兵部队。

Input

第一行包括两个由空格切割开的正整数，分别表示N和M；
接下来的N行，每一行含有连续的M个字符('P'或者'H')。中间没有空格。按顺序表示地图中每一行的数据。N <= 100；M <= 10。

Output

仅一行，包括一个整数K。表示最多能摆放的炮兵部队的数量。

Sample Input

5 4
PHPP
PPHH
PPPP
PHPP
PHHP

Sample Output

与HDU4539基本上一样的题目，仅仅是在推断情况上有些不同而已

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int n,m;
char map[105][15];
int mat[105][15];
int now[1<<10],pre[1<<10],prepre[1<<10];
int l_now,l_pre,l_prepre;
int dp[1<<10][1<<10],tem[1<<10][1<<10],tt[1<<10];

void dfs(int id,int k,int p,int sum)
{
    if(k>=m)
    {
        now[++l_now] = p;
        tt[l_now] = sum;
        return;
    }
    if(k>=2 && mat[id][k] && !(p&(1<<(k-2))) && !(p&(1<<(k-1))))
        dfs(id,k+1,p|(1<<k),sum+1);
    else if(k==1 && mat[id][k] && !(p&(1<<(k-1))))
        dfs(id,k+1,p|(1<<k),sum+1);
    else if(k == 0 && mat[id][k])
        dfs(id,k+1,p|(1<<k),sum+1);
    dfs(id,k+1,p,sum);
}

void solve()
{
    int i,j,k,t;
    tem[1][1] = pre[1] = prepre[1] = 0;
    l_pre = l_prepre = 1;
    for(k = 0; k<n; k++)
    {
        l_now = 0;
        dfs(k,0,0,0);
        for(i = 1; i<=l_now; i++)
            for(j = 1; j<=l_pre; j++)
                dp[i][j] = 0;
        for(i = 1; i<=l_now; i++)
            for(j = 1; j<=l_pre; j++)
                for(t = 1; t<=l_prepre; t++)
                {
                    if(now[i] & prepre[t])   continue;
                    if(now[i] & pre[j]) continue;
                    if(pre[j] & prepre[t]) continue;
                    dp[i][j] = max(dp[i][j],tem[j][t]+tt[i]);
                }
        for(i = 1; i<=l_now; i++)
            for(j = 1; j<=l_pre; j++)
                tem[i][j] = dp[i][j];
        for(i = 1; i<=l_pre; i++)
            prepre[i] = pre[i];
        for(i = 1; i<=l_now; i++)
            pre[i] = now[i];
        l_prepre = l_pre;
        l_pre = l_now;
    }
}

int main()
{
    int i,j,ans;
    while(~scanf("%d%d",&n,&m))
    {
        for(i = 0; i<n; i++)
        {
            scanf("%s",map[i]);
            for(j = 0; j<m; j++)
            {
                if(map[i][j] == 'P')
                    mat[i][j] = 1;
                else
                    mat[i][j] = 0;
            }
        }
        solve();
        ans = 0;
        for(i = 1; i<=l_pre; i++)
            for(j = 1; j<=l_prepre; j++)
                ans = max(ans,tem[i][j]);
        printf("%d
",ans);
    }

    return 0;
}