首页 > 其他 > 详细

状态压缩—玉米田

时间:2020-01-18 23:56:36      阅读:152      评论:0      收藏:0      [点我收藏+]

题面:

农夫约翰的土地由M*N个小方格组成,现在他要在土地里种植玉米。

非常遗憾,部分土地是不育的,无法种植。

而且,相邻的土地不能同时种植玉米,也就是说种植玉米的所有方格之间都不会有公共边缘。

现在给定土地的大小,请你求出共有多少种种植方法。

土地上什么都不种也算一种方法。

输入格式

第1行包含两个整数M和N。

第2..M+1行:每行包含N个整数0或1,用来描述整个土地的状况,1表示该块土地肥沃,0表示该块土地不育。

输出格式

输出总种植方法对100000000取模后的值。

数据范围

1M,N121≤M,N≤12

输入样例:

2 3
1 1 1
0 1 0

输出样例:

9
题解:
骑士那题弱化版,四面八方不能放变为四面不能放。
这里要求值为0的不能放,为了方便,用g[]数组存状态时1表示能放,0表示不能放。
#include<bits/stdc++.h>
using namespace std;
const int N=14,M=1<<12;
int n,m;
int g[N];
vector<int>state;
vector<int>head[M];
long long f[N][M];
bool check(int state)
{
    for(int i=0;i<m;i++)
    {
        if((state>>i&1)&&(state>>i+1&1))
        return false;
    }
    return true;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
     for(int j=0;j<m;j++)
     {
         int t;
         cin>>t;
         g[i]+=!t<<j;//g[i]表示地图,为1不能选,为0时能选
     }
     for(int i=0;i< 1<<m;i++)
     {
         if(check(i))
          state.push_back(i);
     }
     for(int i=0;i<state.size();i++)
      for(int j=0;j<state.size();j++)
       {
           int a=state[i],b=state[j];
           if((a&b)==0)
            head[i].push_back(j);
       }
       f[0][0]=1;
       for(int i=1;i<=n+1;i++)
        for(int a=0;a<state.size();a++)
         for(auto b:head[a])
         {
             if(g[i]&state[a])continue;
             f[i][a]+=f[i-1][b];
             f[i][a]%=100000000;
         }
         cout<<f[n+1][0]<<endl;
    return 0;
}

  



状态压缩—玉米田

原文:https://www.cnblogs.com/flyljz/p/12210565.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!