Submission

Score: 20

User: anak

Problemset: ทางเชื่อม

Language: cpp

Time: 0.694 second

Submitted On: 2026-04-01 04:09:35

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(), (x).end()

const int mod = 1e9+7;
const int MAXN = 5005;
char grid[3][MAXN];
int dp[3][MAXN][6];
void tc() {
    int n;
    cin >> n;
    for(int i=1;i<=2;i++) {
        for(int j=1;j<=n;j++) {
            cin >> grid[i][j];
            for(int k=1;k<=5;k++) dp[i][j][k] = 0;
        }
    }
    for(int i=1;i<=2;i++) {
        if(grid[i][1] == '#') continue;
        for(int k=1;k<=5;k++) {
            dp[i][1][k] = 1;
        }
    }
    dp[1][1][2] = 0;dp[1][1][3] = 0;dp[1][1][4] = 0; dp[2][1][2] = 0;dp[2][1][3] = 0;dp[2][1][5] = 0;
    auto f = [&](int i,int j) {
        if(i == 1) return (dp[i][j][1]%mod + dp[i][j][5]%mod)%mod;
        else return (dp[i][j][1]%mod + dp[i][j][4]%mod)%mod;
    };
    for(int j=2;j<=n;j++) {
        if(grid[1][j] != '#') dp[1][j][3] = (dp[1][j][3]%mod + f(1,j-1)%mod)%mod;
        if(grid[2][j] != '#') dp[2][j][2] = (dp[2][j][2]%mod + f(2,j-1)%mod)%mod;

        if(grid[1][j] != '#') {
            dp[1][j][1] = (dp[1][j][1]%mod + f(1,j-1)%mod)%mod;
            dp[1][j][5] = (dp[1][j][5]%mod + dp[2][j][2]%mod)%mod;
        }
        if(grid[2][j] != '#') {
            dp[2][j][1] = (dp[2][j][1]%mod + f(2,j-1)%mod)%mod;
            dp[2][j][4] = (dp[2][j][4]%mod + dp[1][j][3]%mod)%mod;
        }
    }
    cout << (f(1,n)%mod + f(2,n)%mod)%mod << '\n';
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--) tc();
}