蜜汁TLE求调
查看原帖
蜜汁TLE求调
974277
水星湖psgqwq楼主2024/3/16 10:50
#include <bits/stdc++.h>
#define int long long
using namespace std;
string s[3];
int n;
queue<pair<int,int>> q; 
bool vis[3][200000];

int bfs() {
    while (!q.empty()) q.pop(); 
    q.push({1, 1});
    for(int i=1;i<=2;i++)
        for(int j=1;j<=n;j++)
            vis[i][j] = 0;
    vis[1][1] = 1;

    while (!q.empty()) {
        auto cur = q.front(); q.pop();
        int x = cur.first, y = cur.second;
        if (x == 2 && y == n)
            return 1;

        int dx[] = {0, 0, 1, -1};
        int dy[] = {1, -1, 0, 0};

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 1 || ny < 1 || nx > 2 || ny > n) continue;
            if (s[nx][ny] == '>') ny++;
            else if (s[nx][ny] == '<') ny--;
            
            if (vis[nx][ny]) continue;
            vis[nx][ny] = 1;
            q.push({nx, ny}); 
        }
    }
    return 0;
}

void solve() {
    cin >> n;
    cin >> s[1] >> s[2];
    s[1] = " " + s[1];
    s[2] = " " + s[2]; 
    if (bfs()) cout << "YES" << endl;
    else cout << "NO" << endl;
}

signed main() {
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

2024/3/16 10:50
加载中...