1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 500 5 #define ll long long 6 using namespace std; 7  8 ll dp[maxn][5000]; 9 int h,w;10 ll ans=1;11 void dfs(int i,int t1,int num)12 {13     if(num==w) {dp[i][t1]+=ans; return;}14     dfs(i,t1,num+1);15     if(num<=w-2&&!(t1&1<<num)&&!(t1&(1<<(num+1)))) dfs(i,t1|1<<num|(1<<(num+1)),num+2);16 }17 18 int main()19 {20     while(scanf("%d%d",&h,&w)!=EOF)21     {22         if(h==0&&w==0) break;23         memset(dp,0,sizeof(dp));24         ans=1;25         dfs(1,0,0);26         for(int i=2; i<=h; i++)27         {28             for(int j=0; j<(1<<w); j++)29             {30                 if(dp[i-1][j]) ans=dp[i-1][j];31                 else continue;32                 dfs(i,~j&((1<<w)-1),0);33             }34         }35         printf("%lld\n",dp[h][(1<<w)-1]);36     }37     return 0;38 }

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define ll long long 5 using namespace std; 6  7 int n,m,cur; 8 const int maxn=15; 9 ll d[2][1<<maxn];10 11 void update(int a,int b)12 {13     if(b&(1<<m)) d[cur][b^(1<<m)]+=d[1-cur][a];14 }15 16 int main()17 {18     while(scanf("%d%d",&n,&m)!=EOF)19     {20         if(n==0&&m==0) break;21         memset(d,0,sizeof(d));22         cur=0;23         d[0][(1<<m)-1]=1;24         for(int i=0; i<n; i++)25         {26             for(int j=0; j<m; j++)27             {28                 cur^=1;29                 memset(d[cur],0,sizeof(d[cur]));30                 for(int k=0; k<(1<<m); k++)31                 {32                     update(k,k<<1);33                     if(i&&!(k&(1<<(m-1)))) update(k,(k<<1)^(1<<m)^1);34                     if(j&&!(k&1)) update(k,(k<<1)^3);35 36                 }37             }38         }39         printf("%lld\n",d[cur][(1<<m)-1]);40     }41     return 0;42 }