题意：一个矩形网格，可以填0或1， 但有些位置什么数都不能填，要求相邻两个不同时为1，有多少种填法。矩形大小最大 12*12.

压缩状态DP大多有一个可行的state的范围，先求出这个state范围，对接下来的解题非常有帮助！

注意特判 N==1 的情况。

#include <iostream>

#include <cmath>

#include <cstring>

#include <vector>

using namespace std;

vector<int> t;  // the current map

vector<int> s;  // possible state

int MOD = 100000000;

int dp[15][1<<15];

int main()

{

    //freopen("1.txt","r",stdin);

    int M,N;

    while(cin>>M>>N)

    {

        s.clear(); t.clear();

        for(int tag=0; tag< (1<<N); tag++)

        {

            for(int k=0; k<N-1; k++)

            {

                if((tag &(1<<k)) && (tag &(1<<(k+1)))) break;

                if( k== N-2) s.push_back(tag);

            }

        }

        if(N == 1) {s.push_back(0); s.push_back(1);}

        for(int i=0; i<M; i++)

        {

            int x = 0;

            for(int j=0; j<N; j++)

            {

                int tag; cin>>tag;

                x += tag<<(N - j -1);

            }

            t.push_back(x);

        }

        memset(dp, 0, sizeof(dp));

        for(int i=0; i<s.size(); i++)

        {

            if((s[i] | t[0]) ^ t[0]) continue;

            dp[0][s[i]] = 1;

        }

        for(int i=1; i< M; i++)   // row i

        {

            for(int j=0; j<s.size(); j++)

            {

                if((s[j] | t[i]) ^ t[i]) continue;

                //cout<<"Possible" <<s[j]<<endl;

                // cur state is s[j], pre is s[k];

                for(int k=0; k<s.size(); k++)

                {

                    if(s[j] & s[k]) continue;

                    dp[i][s[j]] += dp[i-1][s[k]];

                    dp[i][s[j]] %= MOD;

                }

            }

        }

        int ret = 0;

        for(int i=0; i<s.size(); i++)

        {

            ret += dp[M-1][s[i]];

            ret %= MOD;

        }

        cout<<ret<<endl;

    }

    return 0;

}

.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, "Courier New", courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }