Submission

Score: 100

User: Bune

Problemset: Croissant Beyond Peaks

Language: cpp

Time: 0.005 second

Submitted On: 2026-02-28 09:06:49

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;

#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define ll long long
#define pb push_back
#define all(x) (x).begin(), (x).end()

int main() {
  fastio

  int Q;
  cin >> Q;
  
  while (Q--) {
    int n;
    string a,b;
    cin >> n >> a >> b;
    pair<int, int> S, T;
    
    for (int i = 0; i < a.size(); i++) {
      if (a[i] == 'S') {
        S.first = 0;
        S.second = i;
      }
      else if (a[i] == 'T') {
        T.first = 0;
        T.second = i;
      }
    }
    for (int i = 0; i < b.size(); i++) {
      if (b[i] == 'S') {
        S.first = 1;
        S.second = i;
      }
      else if (b[i] == 'T') {
        T.first = 1;
        T.second = i;
      }
    }


    // cout << S.first <<" " << S.second << "\n" << T.first << " " << T.second << " ";
    vector<string> v;
    v.pb(a);
    v.pb(b);

    vector<int> dx = {1, 0, -1, 0}, dy = {0, -1, 0, 1};
    vector<vector<bool>> vis(2, vector<bool>(n, false));
    queue<pair<int, int>> q;
    q.push(S);
    vis[S.first][S.second] = true;

    bool found = false;

    while (!q.empty()) {
      auto [x,y] = q.front();
      // cout << "x: " << x << " y: " << y << "\n";
      q.pop();
      if (T.first == x && T.second == y) {
        // cout << "Yes" << "\n";
        found = true;
        break;
      }
      for (int i = 0; i < 4; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (xx < 0 || yy < 0 || xx > 1 || yy > n - 1) continue;
        if (!vis[xx][yy] && v[xx][yy] != '#') {
          q.push({xx, yy});
          vis[xx][yy] = true;
        }
      }
    }

    if (found) cout << "Yes\n";
    else cout << "No\n";

  }

  return 0;
}