﻿POJ 3254 Corn Fields-Ocrosoft

POJ 3254 Corn Fields

Time Limit:2000MS     Memory Limit:65536KB     64bit IO Format:%lld & %llu

Description

Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can’t be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant.

Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant.

Input

Line 1: Two space-separated integers: M and N
Lines 2.. M+1: Line i+1 describes row i of the pasture with N space-separated integers indicating whether a square is fertile (1 for fertile, 0 for infertile)

Output

Line 1: One integer: the number of ways that FJ can choose the squares modulo 100,000,000.

Sample Input

```2 3
1 1 1
0 1 0```

Sample Output

`9`

Hint

Number the squares as follows:

```1 2 3
4  ```

There are four ways to plant only on one squares (1, 2, 3, or 4), three ways to plant on two squares (13, 14, or 34), 1 way to plant on three squares (134), and one way to plant on no squares. 4+3+1+1=9.

Solution

DP的思路就是第i行为状态p的时候，如果第i+1行为状态q且不冲突，那么dp[i+1][p]+=dp[i][p]。

```#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define ms(a) memset(a,0,sizeof(a))
typedef long long ll;
const int INF = INT_MAX;
const int MAXN = 12 + 1;
const int MOD = 100000000;
using namespace std;
int v[1 << MAXN];
int mp[1 << MAXN];//mp也可以不用二进制优化而开成二维
int dp[MAXN][1 << MAXN];
int n, m, t, l;
bool judge(int x)
{
return (x&(x << 1));
//二进制所有位左移一位，最右侧补0，如果原来有相邻的1，那么按位与之后不为0
}
bool check(int i, int x)
{
return (mp[i] & v[x]);
//给出的地和地的某个状态按位与，如果没有冲突就会是0
}
int main()
{
while (cin >> n >> m)
{
ms(dp); ms(v); ms(mp);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
scanf("%d", &t);
if (!t)mp[i] += (1 << (j - 1));//二进制优化
}
}
l = 0;
for (int i = 0; i < (1 << m); i++)
if (!judge(i))v[l++] = i;//枚举出所有本行不冲突的情况
for (int i = 0; i < l; i++)
if (!check(1, i))dp[1][i] = 1;//枚举第一行的状态
for (int i = 2; i <= n; i++)//从第二行开始
{
for (int j = 0; j < l; j++)//枚举所有情况
{
if (check(i, j))continue;//如果第i行给出的地形跟第j中可行状态冲突，不考虑这种状态
for (int k = 0; k < l; k++)
{
if (check(i - 1, k))continue;//如果上一行不满足k状态，跳过
if (!(v[j] & v[k]))dp[i][j] += dp[i - 1][k];//如果第i-1行为k和第i行为j状态不冲突，
//那么第i行j状态可行数量加上i-1行k状态可行数量
}
}
}
int ans = 0;
for (int i = 0; i < l; i++)
ans = (ans + dp[n][i]) % MOD;//第n行所有状态可行数量相加
printf("%d\n", ans);
}
return 0;
}
```