[낙곡P1879] [USACO 06Nov] Corn Fields G

제목 설명

제목: 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.
농장주인 John은 직사각형의 새 목장을 새로 샀는데 이 목장은 M행 N열(1≤M≤12;1≤N≤12)로 나누어져 각 칸마다 정사각형의 땅이다.John은 목장의 몇 칸에 맛있는 풀을 심어 젖소들이 먹을 수 있도록 할 계획이다.
유감스럽게도 일부 토지는 상당히 척박해서 풀을 심는 데 쓸 수 없다.그리고 젖소들은 잔디밭을 독점하는 느낌을 좋아하기 때문에 John은 두 개의 인접한 땅을 선택하지 않는다. 즉, 어느 두 개의 잔디밭도 공공변이 없다는 것이다.
John은 만약 잔디의 총 덩어리 수를 고려하지 않는다면, 모두 몇 가지 재배 방안이 그가 선택할 수 있는지 알고 싶어 한다.(물론 새 목장을 완전히 황폐화하는 것도 방안)

입력 형식

첫 번째 줄: 두 개의 정수 M과 N을 공백으로 구분합니다.
두 번째부터 M+1줄: 줄마다 N개의 빈칸으로 구분된 정수를 포함하여 각 토지의 상태를 설명한다.i+1행은 i행의 토지를 묘사하는데 모든 정수가 0 또는 1이다. 1이면 이 토지가 충분히 비옥하다는 것을 의미하고 0은 이 토지가 풀을 심기에 적합하지 않다는 것을 의미한다.

출력 형식

목장 분배 총 방안의 수를 100,000,0000000000001000000000000의 나머지로 나누는 정수.

출력 샘플 가져오기

#1 입력

2 3
1 1 1
0 1 0

출력 #1

9

분석:

상압 D P DP DP 영(z h e n zhen zhen) 원(d e de) 적 (e e) 신(x i n xin xin)!!!!!!!!!!!!DP DP DP DP DP DP는 말하면 폭력 매거진이지만 ta tata는 2진법이라는 문제를 사용했다. 이진수 ii가 iii의 한 사람이 11이 되면 그 열에는 소 f[i] [j] [i] [j] [j] f[i] [j] [j][j]는 앞의 i가 jjjj 개 상태에서 가장 많은 방안의 수를 나타낸다. 동태적 능량 전이 방정식: f[i] [i] [j] [j] [i] [j] [j] [j] [j] [j][j][j][i] [j][j] [j] [i] [i] [f[j] [i] [j][i] [f[i] [i] [f[i] [j] [i] [[[[[f[[)%mod f[i][j]=(f[i][j]+f[i-3-1][k]) jj는 ii i행의 상태 kk는 i-3-1 i-1 i-3 1행의 상태 g[i] g[i] g[i]로 i상태의 존재 여부를 판단한다. 조건은 ii i의 좌우에 111이 있는지 없는지 ii i의 위치에 존재한다.

CODE：

#include
#include
#define MOD 100000000  //%%%
using namespace std;
int n,m,f[13][1<<12],g[1<<12],a[13][13],OvO[13],ans=0; 
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]);  //              。。
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			OvO[i]=(OvO[i]<<1)+a[i][j];  //     
	for(int i=0;i<(1<<m);i++)
		if(!(i&(i<<1))&&!(i&(i>>1)))  //i    1  1   
		{
			g[i]=1;  //  
			if((i&OvO[1])==i) f[1][i]=1;  //   
		}
	for(int qwq=2;qwq<=n;qwq++)  //  
		for(int j=0;j<(1<<m);j++)
			if(((j&OvO[qwq-1])==j)&&g[j])  //   
				for(int k=0;k<(1<<m);k++)
					if(((k&OvO[qwq])==k)&&!(j&k)&&g[k])  //    
						f[qwq][k]=(f[qwq][k]+f[qwq-1][j])%MOD;  //DP
	for(int i=0;i<(1<<m);i++)
		ans=(ans+f[n][i])%MOD;
	printf("%d",ans);
	return 0;
}