萌新求出bfs红题(cf c)
  • 板块学术版
  • 楼主AKPC
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/3/16 00:37
  • 上次更新2024/3/16 10:10:59
查看原帖
萌新求出bfs红题(cf c)
540363
AKPC楼主2024/3/16 00:37
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mpr make_pair
#define fr first
#define sc second
const int N=6e5+5;
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int n,a[2][N];
bool tmp[2][N];
queue<pair<int,int> >q;
signed main(){
	int T;
	cin>>T;
	while (T--){
		cin>>n;
		for (int i=1;i<=2;i++){
			for (int j=1;j<=n;j++){
				char ch;cin>>ch;
				a[i][j]=(ch=='>')*2-1;
				tmp[i][j]=0;
			}
		}
		q.push(mpr(1,1));
		bool ss=0;
		while (!q.empty()&&!ss){
			int x=q.front().fr,y=q.front().sc;
			q.pop();
			if (x==2&&y==n){
				ss=1;
				break;
			}
			for (int i=0;i<4;i++){
				int cx=x+dx[i],cy=y+dy[i];
				if (cx<1||cy<1||cx>2||cy>n) continue;
				if (!tmp[cx][cy]){
					if (cx==2&&cy==n){
						ss=1;
						break;
					}
					if (cy+a[cx][cy]>n||cy+a[cx][cy]<1) continue;
					if (tmp[cx][cy+a[cx][cy]]) continue;
					q.push(mpr(cx,cy+a[cx][cy])),tmp[cx][cy+a[cx][cy]]=1;
				}
			}
		}
		if (ss) cout<<"YES\n";
		else cout<<"NO\n";
		while (!q.empty()) q.pop();
	}
	return 0;
}

RE#3

2024/3/16 00:37
加载中...