POJ 2411 압축 상태 DP

이 제목 대박!직사각형을 정하고 1*2의 칸으로 덮어쓰도록 하는데 몇 가지 덮어쓰는 방법이 있나요?
dp[i][j]상태가 j이고 i줄이 완전히 깔린 상황에서 종류수는 몇 가지입니까?j 중 1은 차지를 표시하고, 0은 차지를 표시하지 않았다.
모든 줄이 놓인 후에 어떤 상태는 불가능한 것이 분명하다. 우리는 여기서 1을 세로로 하고 0을 가로로 한다.그래서 두 개의 0은 서로 인접해야 한다. 이것은 프로그램의 s이다.
우리는 모든 상태가 이동하고 모든 가능한 상태를 열거한다. 우리는 dp[i][j]의 j가 s[k]의 상태를 보이고 순서대로 상태 이동을 진행하기를 바란다.

#include <iostream>

#include <vector>

#include <cstring>

using namespace std;



vector<int> s;  // possible state

long long dp[13][1<<12];  // dp[i][j]  the number of (row i state j)



int main()

{

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

    int M,N;

    while(cin>>M>>N && M!=0 && N!=0)

    {

        s.clear();

        if(M*N%2) {cout<<0<<endl; continue;}

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

        // 0-0 pair

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

        {

            for(int i=0; i<N; )

            {

                if(tag & (1<<i)) i++;

                else

                {

                    if( i+1< N && !(tag&(1<<(i+1)))) i+=2;

                    else break;

                }

                if(i== N) s.push_back(tag);

            }

        }

        for(int i=0; i<s.size(); i++) dp[0][s[i]] = 1;

        for(int step = 1; step< M; step++)

        {

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

            {

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

                {

                    if((tag & s[i]) != tag) continue;

                    dp[step][tag^ s[i]] += dp[step-1][tag];

                }

            }

        }

        cout<<dp[M-1][0]<<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; }