TopCoder SRM 504 Div1 Medium: AlgridTwo

解法

mayokoex.hatenablog.com

h+1行目はh行目から生成される上に、h行目は与えられているので、そのh+1行目を作る時だけ考えれば良い。

• h行目から生成したh+1行目がoutputのh+1と矛盾する場合、答は0である。
• 矛盾しない場合、元のh+1行めの中の塗りつぶされてしまうマスは、何色でも良い。このマスの数をcとすると答はとなる。

コード

import java.math.BigInteger;

public class AlgridTwo {
	private final int MOD = 1000000007;

	public int makeProgram(String[] output) {
		int H = output.length;
		int W = output[0].length();
		char[][] grid = new char[H][W];

		int cnt = 0;
		for (int h = 0; h < H - 1; h++) {
			for (int w = 0; w < W; w++) {
				grid[h][w] = output[h].charAt(w);
			}

			// 最初は?を入れておく
			for (int w = 0; w < W; w++) {
				grid[h + 1][w] = '?';
			}

			// 擬似コードを実装した部分
			for (int w = 0; w < W - 1; w++) {
				if (grid[h][w] == 'W' && grid[h][w + 1] == 'W') {
					continue;
				}
				if (grid[h][w] == 'B' && grid[h][w + 1] == 'W') {
					grid[h + 1][w] = 'B';
					grid[h + 1][w + 1] = 'B';
				}
				if (grid[h][w] == 'W' && grid[h][w + 1] == 'B') {
					grid[h + 1][w] = 'W';
					grid[h + 1][w + 1] = 'W';
				}
				if (grid[h][w] == 'B' && grid[h][w + 1] == 'B') {
					char tmp = grid[h + 1][w];
					grid[h + 1][w] = grid[h + 1][w + 1];
					grid[h + 1][w + 1] = tmp;
				}
			}

			for (int w = 0; w < W; w++) {
				if (grid[h + 1][w] != '?') {
					// ?でない部分は塗りつぶされているので、元が何色でも関係ない
					if (grid[h + 1][w] != output[h + 1].charAt(w)) {
						// 矛盾している時
						return 0;
					}
					cnt++;
				}
			}
		}

		long ans = modPow(2, cnt);
		return (int) ans;
	}

	private long modPow(int n, int k) {
		BigInteger twoInteger = new BigInteger(String.valueOf(n));
		BigInteger cntInteger = new BigInteger(String.valueOf(k));
		BigInteger ansInteger = twoInteger.modPow(cntInteger, new BigInteger(
				String.valueOf(MOD)));
		return ansInteger.longValue();
	}

}