Problem Description
鄭廠長不是正廠長
也不是副廠長
他根本就不是廠長
事實上
他是帶兵打仗的團長
一天，鄭廠長帶著他的軍隊來到了一個n*m的平原准備布陣。
根據以往的戰斗經驗，每個士兵可以攻擊到並且只能攻擊到與之曼哈頓距離為2的位置以及士兵本身所在的位置。當然，一個士兵不能站在另外一個士兵所能攻擊到的位置，同時因為地形的原因平原上也不是每一個位置都可以安排士兵。
現在，已知n,m 以及平原陣地的具體地形，請你幫助鄭廠長計算該陣地,最多能安排多少個士兵。
Input
輸入包含多組測試數據；
每組數據的第一行包含2個整數n和m (n <= 100, m <= 10 )，之間用空格隔開；
接下來的n行，每行m個數，表示n*m的矩形陣地，其中1表示該位置可以安排士兵，0表示該地形不允許安排士兵。
Output
請為每組數據計算並輸出最多能安排的士兵數量，每組數據輸出一行。
Sample Input
6 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
Sample Output
2 比較簡單的狀態壓縮 #include
#include
#include
using namespace std;
int map[105][15];
int dp[1<<10][1<<10],tem[1<<10][1<<10];
int now[1<<10],pre[1<<10],prepre[1<<10],ans[1<<10];
int l_now,l_pre,l_prepre;
int n,m;
void dfs(int id,int k,int p,int sum)
{
if(k>=m)
{
now[++l_now] = p;
ans[l_now] = sum;
return;
}
if(k>=2 && map[id][k] && !(p&(1<<(k-2))))//這格可以放，而左邊第二格不能放，那麼在這個位置放下
dfs(id,k+1,p|(1<>1)) continue;
if(now[i] & (pre[j]<<1)) continue;
dp[i][j] = max(dp[i][j],tem[j][t]+ans[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;
while(~scanf("%d%d",&n,&m))
{
for(i = 0; i
