Submission

PP-TTTTTTT

Score: 20

User: mydKN

Problemset: ทางเชื่อม

Language: cpp

Time: 1.090 second

Submitted On: 2025-03-31 20:21:25

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const ll mod = 1e9 + 7;
const int di[] = {0, 0, -1, 1};
const int dj[] = {1, -1, 0, 0};
const int maxn = 5005;

ll memo[2][maxn][3];

ll solve(int ui, int uj, int state, vector<vector<bool>> &grid, int &n){
	if(uj >= n) return 1LL;
	if(!grid[ui][uj]) return 0LL;
	if(memo[ui][uj][state] != -1) return memo[ui][uj][state];
	ll cnt = 0;
	grid[ui][uj] = 0;
	// cout << ui << " " << uj << "\n";
	if(state == 1){
		// cout << ui << " " << uj << "\n";
		if(uj + 1 >= n || grid[ui][uj+1]){
			cnt = (cnt + solve(ui, uj+1, 1, grid, n)) % mod;
		}
		if(ui - 1 >= 0 && grid[ui-1][uj]){
			cnt = (cnt + solve(ui-1, uj, 2, grid, n)) % mod;
		}
		if(ui + 1 < 2 && grid[ui+1][uj]){
			cnt = (cnt + solve(ui+1, uj, 3, grid, n)) % mod;
		}
	}
	else if(state == 2 || state == 3){
		if(uj + 1 >= n || grid[ui][uj+1]){
			cnt = (cnt + solve(ui, uj+1, 1, grid, n)) % mod;
		}
	}
	grid[ui][uj] = 1;
	return memo[ui][uj][state] = cnt;
}

void mains(){
	int n;
	cin >> n;
	vector<vector<bool>> grid(2, vector<bool>(n+5));
	memset(memo, -1, sizeof(memo));
	for(int i=0;i<2;++i){
		for(int j=0;j<n;++j){
			char ch;
			cin >> ch;
			if(ch == '.') grid[i][j] = 1;
			else grid[i][j] = 0;
			// cout << grid[i][j];
		}
		// cout << "\n";
	}
	cout << (solve(0, 0, 1, grid, n) + solve(1, 0, 1, grid, n)) % mod << "\n";
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int q;
	cin >> q;
	while(q--) mains();
}