Submission

Score: 0

User: august

Problemset: ทางเชื่อม

Language: cpp

Time: 1.095 second

Submitted On: 2026-03-19 22:37:37

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9+7;

int l;

int fnd(int i, int j, int state, vector<vector<vector<int>>> &dp, vector<string> &g) {
    if (i<0 || i>1 || (j < l && g[i][j] == '#')) return 0;
    if (j == l) {
        if (state == 0) return 1;
        return 0;
    }

    if (dp[i][j][state] != -1) return dp[i][j][state];

    int sm = 0;
    if (state == 0) {
        sm = (fnd(i, j+1, 0, dp, g)+sm)%MOD;
        sm = (fnd(i, j+1, 1, dp, g)+sm)%MOD;
        sm = (fnd(i, j+1, 2, dp, g)+sm)%MOD;    
    }
    else if (state == 1) {
        sm = (fnd(i-1, j, 4, dp, g)+sm)%MOD;
    }
    else if (state == 2) {
        sm = (fnd(i+1, j, 3, dp ,g)+sm)%MOD;
    }
    else if (state == 3) {
        sm = (fnd(i, j+1, 0, dp, g)+sm)%MOD;
        sm = (fnd(i, j+1, 1, dp, g)+sm)%MOD;
    }
    else if (state == 4) {
        sm = (fnd(i, j+1, 0, dp, g)+sm)%MOD;
        sm = (fnd(i, j+1, 3, dp, g)+sm)%MOD;
    }
    return dp[i][j][state] = sm;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin>> n;

    while (n--) {
        cin>> l;

        vector<vector<vector<int>>> dp(2, vector<vector<int>>(l+1, vector<int>(5, -1)));
        vector<string> g(2);
        for (int i=0; i<2; i++) cin>> g[i];

        int sm = 0;
        for (int i=0; i<2; i++) {
            for (int j=0; j<3; j++) {
                sm = (fnd(i, 0, j, dp, g)+sm)%MOD;
            }
        }
        cout<<sm<< '\n';
    }
}