AOJ0559/JOI Flag

AOJ0559.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class AOJ0559 {
	public static int MOD = 100000;
	
	public static void main(String[] args) throws IOException {
		BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
		String[] data = r.readLine().split(" ");
		int m = Integer.valueOf(data[0]);
		int n = Integer.valueOf(data[1]);
		int[][] map = new int[m][n];
		int[] cmap = new int[512];
		cmap['J'] = 0;
		cmap['O'] = 1;
		cmap['I'] = 2;
		cmap['?'] = -1;
		for (int i = 0 ; i < m ; i++) {
			String line = r.readLine();
			for (int j = 0 ; j < n ; j++) {
				map[i][j] = cmap[line.charAt(j)];
			}
		}
		
		int pushnext = (1<<(n-2));
		int[][] dp = new int[1<<n][2];
		int[][] dp_next = new int[1<<n][2];
		dp[0][0] = 1;
		for (int y = 0 ; y < m ; y++) {
			for (int x = 0 ; x < n ; x++) {
				boolean[] canput = new boolean[3];
				if (map[y][x] == -1) {
					Arrays.fill(canput, true);
				} else {
					canput[map[y][x]] = true;
				}
				for (int ptn = 0 ; ptn < 1<<(n-1) ; ptn++) {
					for (int prev = 0 ; prev <= 1 ; prev++) {
						if (dp[ptn][prev] >= 1) {
							int base = dp[ptn][prev];
							int nptn = ptn / 2;
							int nxptn = nptn | pushnext;
							if (x == n - 1) {
								if (prev == 1) {
									if (canput[1]) {
										dp_next[nxptn][0] += base;
										dp_next[nxptn][0] %= MOD;
									}
									int cnt = ((canput[0]) ? 1 : 0) + ((canput[2]) ? 1 : 0);
									dp_next[nptn][0] += base * cnt;
									dp_next[nptn][0] %= MOD;
								} else {
									int cnt = ((canput[0]) ? 1 : 0) + ((canput[1]) ? 1 : 0) + ((canput[2]) ? 1 : 0);
									dp_next[nptn][0] += base * cnt;
									dp_next[nptn][0] %= MOD;									
								}
								continue;
							}
							
							if ((ptn & 1) == 1) {
								// JO
								// ?
								if (prev == 1) {
									//  JO
									// J?

									// O
									if (canput[1]) {
										dp_next[nxptn][0] += base;
										dp_next[nxptn][0] %= MOD;
									}
									// J
									if (canput[0]) {
										dp_next[nptn][1] += base;
										dp_next[nptn][1] %= MOD;
									}
								} else {
									//  JO
									// .?

									// O
									if (canput[1]) {
										dp_next[nptn][0] += base;
										dp_next[nptn][0] %= MOD;
									}
									
									// J
									if (canput[0]) {
										dp_next[nptn][1] += base;
										dp_next[nptn][1] %= MOD;
									}
								}
							} else {
								// ..
								// ?
								if (prev == 1) {
									//  ..
									// J?
									
									// O
									if (canput[1]) {
										dp_next[nxptn][0] += base;
										dp_next[nxptn][0] %= MOD;
									}
									
									// J
									if (canput[0]) {
										dp_next[nptn][1] += base;
										dp_next[nptn][1] %= MOD;
									}	
									
									// I
									if (canput[2]) {
										dp_next[nptn][0] += base;
										dp_next[nptn][0] %= MOD;
									}
								} else {
									//  ..
									// .?
									
									// O,I
									int cnt = ((canput[1]) ? 1 : 0) + ((canput[2]) ? 1 : 0);
									dp_next[nptn][0] += base * cnt;
									dp_next[nptn][0] %= MOD;
									
									// J
									if (canput[0]) {
										dp_next[nptn][1] += base;
										dp_next[nptn][1] %= MOD;
									}
								}
							}
						}
					}
				}
				
				for (int ptn = 0 ; ptn < 1<<(n-1) ; ptn++) {
					for (int prev = 0 ; prev <= 1 ; prev++) {
						dp[ptn][prev] = dp_next[ptn][prev];
						dp_next[ptn][prev] = 0;
					}
				}
			}
		}
		
		int tans = 1;
		for (int y = 0 ; y < m ; y++) {
			for (int x = 0 ; x < n ; x++) {
				if (map[y][x] == -1) {
					tans = (tans * 3) % MOD;
				}
			}
		}
		
		int ans = 0;
		for (int ptn = 0 ; ptn < 1<<n ; ptn++) {
			for (int prev = 0 ; prev <= 1 ; prev++) {
				ans += dp[ptn][prev];
				ans %= MOD;
			}
		}
		System.out.println(((tans - ans) + MOD) % MOD);
	}
}