UVa 11957 - Checkers

// UVa 11957 - Checkers

#include <iostream>
#include <string>
#include <string.h>
#include <stdio.h>
using namespace std;

#define MaxN 101
#define Mod 1000007

int main() {
	int tt;
	cin >> tt;
	for (int t = 1; t <= tt; t++) {
		// input
		int n;
		cin >> n;
		string board[MaxN];
		getline(cin, board[0]);
		for (int y = n; y > 0; y--)
			getline(cin, board[y]);
		// base cases
		int T[MaxN][MaxN];
		memset(T, 0, sizeof(T));
		// DP
		for (int y = 1; y <= n; y++) {
			for (int x = 0; x < n; x++)
				if (board[y][x] == 'B')
					T[y][x] = 0;
				else if (board[y][x] == 'W')
					T[y][x] = 1;
				else {
					int sum = 0;
					if (x > 0 && board[y - 1][x - 1] != 'B')
						sum += T[y - 1][x - 1];
					if (x > 1 && y >= 1 && board[y - 1][x - 1] == 'B'
							&& board[y - 2][x - 2] != 'B')
						sum += T[y - 2][x - 2];
					if (x + 1 < n && board[y - 1][x + 1] != 'B')
						sum += T[y - 1][x + 1];
					if (x + 2 < n && y - 2 >= 0 && board[y - 1][x + 1] == 'B'
							&& board[y - 2][x + 2] != 'B')
						sum += T[y - 2][x + 2];
					sum %= Mod;
					T[y][x] = sum;
				}
		}
		// output
		int sol = 0;
		for (int x = 0; x < n; x++)
			sol = (sol + T[n][x]) % Mod;
		printf("Case %d: %d\n", t, sol);
	}
	return 0;
}