POJ 3254 Corn Fields状態圧縮DP(C++/Java)

http://poj.org/problem?id=3254
テーマ:
1人の農民がn行m列の場所を持っていて、各格子は1で芝生を植えることができて、0はできません.牛を放すには芝生があるしかありませんが、隣の芝生では同時に牛を放すことはできません.全部で何種類の方法がありますか.
考え方:
状態圧縮のDP.
放牧状況をバイナリ数字で表し、その状態が条件を満たしているか否かを判断することができる.
この問題の制限条件は2つあります.
1.芝生制限.
2.隣接する制限.
芝生制限については,入力時1は芝生を植えることができるからである.
「11110」の草地分析では、最後の1つだけ草を植えてはいけない. .(なぜ反逆するのか?反逆しないで反例を挙げることができる)
状態10101が隣接していないと仮定しますが、10101 & 00001!=0は競合を示します.
隣接する制限については、同じ行の制限と上下の2行の制限に分けられます.
同じ行の制限は最初に隣接する状況をすべて取り除くことができて、一致する格納配列は、状態数を減らすのに役立ちます.これも解決しました.
上下2行を合わせればよい.
例えば(仮に草を植えることができると仮定する)
10101&00100!=0も衝突しています.
OKにコードを付けます.
C++:

#include<cstdio>
#include<cstring>
const int mod = 100000000;
const int MAXN = 1 << 12;
int map[20], status[MAXN], dp[20][MAXN];
int len;

int main()
{
	int n, m;
	while (~scanf("%d%d", &n, &m))
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				int temp;
				scanf("%d", &temp);
				if (!temp)
					map[i] = map[i] | (1 << (m - j - 1));
			}
		}
		
		len = 0;
		int tot = 1 << m;
		//    
		for (int i = 0; i < tot; i++)
		{
			//      
			if ((i &(i >> 1)) == 0)  status[len++] = i;
		}
		//      
		memset(dp, 0, sizeof(dp));
		for (int i = 0; i <len ; i++)
		{
			if ((status[i] & map[0]) == 0)
				dp[0][i] = 1;
		}

		for (int i = 1; i < n; i++)
		{
			for (int j = 0; j < len; j++)
			{
				if ((status[j] & map[i-1]) != 0) continue;
				for (int k = 0; k < len; k++)
				{
					if ((status[k] & map[i]) != 0)  continue;
					if ((status[k] & status[j]) != 0)  continue;
					dp[i][k] = (dp[i][k] +dp[i - 1][j] )% mod;
				}
			}
		}
		int ans = 0;
		for (int i = 0; i < len; i++)
			ans = (ans + dp[n - 1][i]) % mod;
		printf("%d
", ans);
	}
	return 0;
}

JAVA:

import java.util.Scanner;

public class Main {

	final static int mod = 100000000;
	final static int MAXN = 1 << 12;
	static int[] map = new int[20];
	static int[] status = new int[MAXN];
	static int[][] dp = new int[20][MAXN];
	static int len;

	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int n, m;
		while (cin.hasNext()) {
			n = cin.nextInt();
			m = cin.nextInt();
			init(n,m);

			for (int i = 0; i < n; i++)
				for (int j = 0; j < m; j++) {
					int temp = cin.nextInt();
					if (temp ==0)
						map[i] = (map[i] | (1 << (m - j - 1)));
				}

			int tot = 1 << m;
			len = 0;
			for (int i = 0; i < tot; i++)
				if ((i & (i << 1)) == 0) {
					status[len++] = i;
				}

			for (int i = 0; i < len; i++) {
				if ((map[0] & status[i]) == 0)
					dp[0][i] = 1;
			}

			for (int i = 1; i < n; i++) {
				for (int j = 0; j < len; j++) {
					if ((map[i - 1] & status[j]) != 0)
						continue;
					for (int k = 0; k < len; k++) {
						if ((map[i] & status[k]) != 0)
							continue;
						if ((status[j] & status[k]) != 0)
							continue;
						dp[i][k] = (dp[i][k] + dp[i - 1][j]) % mod;
					}
				}
			}
			int ans = 0;
			for (int i = 0; i < len; i++) {
				ans = (ans + dp[n - 1][i]) % mod;
			}
			System.out.println(ans);
		}
	}

	public static void init(int n,int m)
	{
		int tot=1<<m;
		for(int i=0;i<n;i++)
		{	
			map[i]=0;
			for(int j=0;j<tot;j++)
				dp[i][j]=0;
		}
	
		
	}
}