상태 압축 dp poj 3254 Corn Fields

Corn Fields
Time Limit: 2000MS
 
Memory Limit: 65536K
Total Submissions: 13187
 
Accepted: 6911
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.
Source
USACO 2006 November Gold
제목 대의:
n*m의 공터를 주고 각 공터의 상태를 준다. 1은 소를 방목할 수 있고 0은 소를 방목할 수 없다. 그리고 두 소는 서로 인접할 수 없다. 몇 가지 안배 방식이 있는지 물어보는데 그 중 한 마리도 방목하지 않는 것도 하나의 방식이다.
아이디어:
이것은 상압 dp의 입문 제목이다. 각 줄의 상태에 대해 우리는 이진 숫자로 표시한다. 예를 들어 첫 번째 줄 101001은 첫 번째 공터에서 소를 방목하고 세 번째 공터에서 소를 방목하고 여섯 번째 공터에서 소를 방목한다. 나머지 각 줄의 상태는 모두 이렇게 표시한 다음에 현재 상태가 합법적인지 아닌지를 판정한다. 만약에 현재 상태가 합법적이라면 실행 가능한 상황이다. 합치면 마지막에 답이다.
상태: dp[i][j]가 i행 상태 j일 때의 배열 방안,
초기값: 첫 번째 행의 모든 올바른 상태는 1입니다.
우리는 모두 dp가 가장 중요한 것은 상태 이동 방정식이라는 것을 알고 있다. 그러면 이런 상태 이동 방정식은 어떻게 씁니까?
우리는 우선 모든 단행의 합법적인 상태를 매거하고, i행의 j종 상태를 매거하며, i-1행의 k종 상태를 매거한다. 만약 두 상태가 충돌하지 않는다면
dp [ i ] [ j ] + = dp[ i - 1] [ k ] 
마지막 줄의 모든 값을 더하면 답이다.
자, 여기까지 하겠습니다. 한 상태가 합법적인지 아닌지를 어떻게 판단합니까?
만족해야 하는 조건: 좌우의 두 개 1은 인접할 수 없음(두 소는 인접할 수 없음), 상태 i & (i<<1)==0
비옥한 토지만 소 방목(토지의 제한)상태 i &map [j]==0상태 i & 현재 행지도
상하의 소가 서로 인접하지 않는 i&j==0i는 현재 줄 상태 j는 전 줄의 상태입니다. 
소감:
이 문제를 잘 이해하면 많은 문제를 풀 수 있다. 정말,
AC 코드:

#include 
#include 
#include 
using namespace std;
const int mod = 100000000;
const int maxx=1<<12+1;
int n,m;
int mapp[15];
int all[maxx];
int dp[15][maxx];
bool isok(int f,int s)
{
    return (mapp[f]&all[s]);
}
int main()
{
    int i,j,t;
    while(~scanf("%d%d",&n,&m))
    {
        int k=0;
        memset(mapp,0,sizeof(mapp));
        memset(dp,0,sizeof(dp));
        memset(all,0,sizeof(all));
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                scanf("%d",&t);
                if(t==0)
                {
                    mapp[i]+=(1<