Submission

Score: 100

User: anak

Problemset: ทางเชื่อม

Language: cpp

Time: 0.799 second

Submitted On: 2026-04-01 04:16:58

#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;
        }
    }
    if(grid[1][1] != '#') {
        dp[1][1][1] = 1;
        dp[1][1][5] = (grid[2][1]=='#'? 0 : 1);
    }
    if(grid[2][1] != '#') {
        dp[2][1][1] = 1;
        dp[2][1][4] = (grid[1][1]=='#'? 0 : 1);
    }
    auto f = [&](int i,int j) {
        if(grid[i][j] == '#') return 0;
        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 + (grid[2][j] != '#' ? dp[2][j][2]%mod : 0))%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 + (grid[1][j] != '#'? dp[1][j][3]%mod : 0))%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();
}