範例程式碼 uva11957

//uva11957
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    int T = 0;

    cin >> T;
    for (int i = 0; i < T; i++) {
        int bsize = 0, ans = 0;

        cin >> bsize;
        vector<string> board(bsize, "");
        vector<vector<int>> dp(bsize, vector<int>(bsize + 2, 0));

        for (int j = bsize - 1; j >= 0; j--) {
            string temp;

            cin >> temp;
            board.at(j) = temp;
        }

        for (int j = 1; j < bsize; j++) {
            for (int k = 0, l = 1; k < bsize; k++, l++) {
                if (board[j][k] == 'W' || board[j][k] == 'B') continue;

                if (board[j - 1][k - 1] == 'W' || board[j - 1][k + 1] == 'W') {
                    dp[j][l] = 1;
                } else {
                    if (j >= 2 && board[j - 1][k - 1] == 'B') {
                        if (board[j - 2][k - 2] == 'W') {
                            dp[j][l] = 1;
                            continue;
                        }
                        dp[j][l] += dp[j - 2][l - 2];
                    } else {
                        dp[j][l] += dp[j - 1][l - 1];
                    }
                    if (j >= 2 && board[j - 1][k + 1] == 'B') {
                        if (board[j - 2][k + 2] == 'W') {
                            dp[j][l] = 1;
                            continue;
                        }
                        dp[j][l] += dp[j - 2][l + 2];
                    } else {
                        dp[j][l] += dp[j - 1][l + 1];
                    }
                }
                dp[j][l] %= 1000007;
                if (j == bsize - 1) {
                    ans += dp[j][l];
                }
            }
        }
        cout << "Case " << i + 1 << ": " << ans % 1000007 << endl;
    }
    return 0;
}