[상압 dp] poj3254

Corn Fields
Time Limit: 2000MS
 
Memory Limit: 65536K
Total Submissions: 6106
 
Accepted: 3235
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.
n*m의 토지를 주어 농사를 지을 수 없고, 토지가 있으면 농사를 지을 수 없으며, 각 토지마다 코란이 있는 토지는 임변이 있을 수 없으며, 방안이 몇 가지가 있느냐고 묻는다.
n과 m의 그 작은 범위를 보면 상압 dp라는 것을 알 수 있다...오랫동안 상압을 건드리지 않아서 좀 허전하다......
이른바 상태 압축이란 2진법(또는 3진법 4진법 등)으로 상태를 표시하고 비트 연산을 통해 이동할 수 있는지 없는지를 판단하는 것이다
우선 일괄적으로 행할 수 있는 모든 상태를 열거해야 한다. 즉, 두 개의 인접한 상태가 없다. 판단 방법은 (i&(i>>1)==0)이다.
그리고 방정식을 옮기는 것은 다음과 같다.
만약 k번째 상태가 i행에서 실행될 수 있다면 (a[i] &state[k]) 이전 줄 상태가 j번째 줄과 충돌하지 않음(state[k] &state[j])==0)
f[k][i]  +=  f [j] [i - 1];
경계에 주의하라고 일깨워라, 나는 첫 줄을 먼저 단독으로 처리하여 경계를 만드는 습관이 있다!
ps: 01로 스크롤 가능...
이 문제를 풀 때 여러 가지 문제가 나왔다. 예를 들어 처음에 방안 수를 모범으로 삼아야 한다는 것을 보지 못했고 더 심각한 것은 첫 줄을 단독으로 처리할 때 실행 가능한지 아닌지를 판단하지 못했다는 것이다.
) 그리고 스크롤 수조 스크롤 과정 중 0이 없어...그리고 이런 갖가지 문제 때문에 화려하게 5번...교훈을 얻었구나.

#include <iostream>
#include <cstring>
#include <cstdio>
const long N = 14, SUM = 4100;

long n, m, t;
long a[N];
long f[SUM][2];
long state[SUM];
using namespace std;
int main()
{
    freopen("poj3254.in", "r", stdin);
    memset(state, 0 , sizeof(state));
    while (scanf("%d%d", &n, &m) != EOF)
    {
        long tmp;
        for (long i = 1; i <= n; i++)
        {
            a[i] = 0;
            for (long j = 1; j <= m; j++)
            {
                scanf("%d", &tmp);
                if (tmp != 1)
                {
                    a[i] = a[i] + (1 << (j - 1));
                }
            }
        }
        t = 0 ;
        long r = (1 << m) - 1;
        for (long i = 0; i <= r; i++)
        {
            if ((i & (i >> 1)) == 0)
                state[++t] = i;
        }
        
        memset(f, 0, sizeof(0));
        for (long i = 1; i <= t; i++)
        {
            if ((a[1] & state[i]) == 0) f[i][0] =  1;
        }


        long p = 0;
        long q = 1;
        for (long i = 2; i <= n; i++)
        {
            for (long j = 1; j <= t; j++)
                f[j][q] = 0;
            for (long j = 1; j <= t; j++)
            for (long k = 1; k <= t; k++)
            {
                if (((state[k] & state[j]) == 0)&&((a[i] & state[k]) == 0))
                {

                    f[k][q] = (f[k][q] + f[j][p])% 100000000;
                   // cout << state[k]<<' '<<state[j] <<' '<< f[k][q] << endl;
                }
            }
            p = p ^ 1;
            q = q ^ 1;
        //cout << endl;
        }
        long re = 0;
        for (long i = 1; i <= t; i++)
        {
            re = (re + f[i][p]) % 100000000;
        }
        cout << re <<endl;



    }
    return 0;
}