Submission

Score: 0

User: theem1502

Problemset: ทางเชื่อม

Language: cpp

Time: 1.096 second

Submitted On: 2026-03-14 00:18:59

#include <bits/stdc++.h>
using namespace std;
int dix[3] = {1,0,-1};
int diy[3] = {0,1, 0};
int recursion(int currentx, int currenty, vector<string> &thearray, int collumn, vector<vector<bool>> &visited, vector<vector<int>> &dp)  {
  //  cout << "c " << currentx << " " << currenty << "\n";
    if (currenty >= collumn) return 1;
    if (currentx >= 2 || currentx < 0||currenty >= collumn) {
        return 0;
    }


    if (thearray[currentx][currenty] == '#' || visited[currentx][currenty]) {/*cout << "w" ; */return 0; }
    if (dp[currentx][currenty] != -1) return dp[currentx][currenty];
    visited[currentx][currenty] = true;
    int sum = 0;
    for (int i = 0; i < 3; i++) {
        sum += recursion(currentx + dix[i], currenty + diy[i], thearray, collumn, visited, dp);
    }
    visited[currentx][currenty] = false;
    return dp[currentx][currenty] = sum;


}

 void solve() {
    int num;
    cin >> num;
    vector<string> thearray(2);
    for (int i = 0; i < 2; i++) cin >> thearray[i];
    vector<vector<bool>> visited(2, vector<bool> (num, false)), secvi(2, vector<bool> (num, false));
    vector<vector<int>> dp(2, vector<int> (num, -1)); vector<vector<int>> secdp(2, vector<int> (num, -1));
    cout << recursion(1,0,thearray,num, visited, dp)  + recursion(0,0,thearray, num, secvi, secdp) << "\n";


 }

int main() {
    int t;
    cin >> t;
    while(t--) solve();

}