求助,#1 #3 AC,其他都 WA 了
查看原帖
求助,#1 #3 AC,其他都 WA 了
592238
Elairin176楼主2023/1/1 08:06
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int n,m,sx,sy,dx[4]={1,-1,0,0},dy[4]={0,0,1,-1},cnt[4][2000];
char mp[2000][2000];
bool vis[5][2000][2000],brk;
struct pos{
	int x;
	int y;
	int type;//1 is first,2 is second
};
queue<pos>q;
int main(void){
	//freopen("data.txt","r",stdin);
	while(cin>>n>>m){
		while(!q.empty()){
			q.pop();
		}
		brk=false;
		memset(vis,0,sizeof(vis));
		memset(cnt,0,sizeof(cnt));
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				cin>>mp[i][j];
				if(mp[i][j]=='S'){
					mp[i][j]='.';
					sx=i;
					sy=j;
				}
			}
		}
		q.push(pos{sx,sy,1});
		while(!q.empty()){
			int x=q.front().x,y=q.front().y,flag=q.front().type;
			q.pop();
			if(flag==2&&x==sx&&y==sy){
				brk=true;
				cout<<"Yes";
				break;
			}
			for(int i=0;i<4;i++){
				int xx=x+dx[i],yy=y+dy[i];
				if(xx<0){
					xx=n-1;
					if(mp[xx][yy]=='#'){
						continue;
					}
					if(vis[2][xx][yy]){
						continue;
					}
					vis[2][xx][yy]=true;
					cnt[0][yy]++;
					if(cnt[0][yy]==cnt[1][yy]){
						cnt[0][yy]--;
						vis[2][xx][yy]=false;
						continue;
					}
					q.push(pos{xx,yy,2});
				}else if(xx>=n){
					xx=0;
					if(mp[xx][yy]=='#'){
						continue;
					}
					if(vis[2][xx][yy]){
						continue;
					}
					cnt[1][yy]++;
					vis[2][xx][yy]=true;
					if(cnt[0][yy]==cnt[1][yy]){
						cnt[1][yy]--;
						vis[2][xx][yy]=false;
						continue;
					}
					q.push(pos{xx,yy,2});
				}else if(yy<0){
					yy=m-1;
					if(mp[xx][yy]=='#'){
						continue;
					}
					if(vis[2][xx][yy]){
						continue;
					}
					cnt[2][xx]++;
					vis[2][xx][yy]=true;
					if(cnt[2][xx]==cnt[3][xx]){
						cnt[2][xx]--;
						vis[2][xx][yy]=false;
						continue;
					}
					q.push(pos{xx,yy,2});
				}else if(yy>=m){
					yy=0;
					if(mp[xx][yy]=='#'){
						continue;
					}
					if(vis[2][xx][yy]){
						continue;
					}
					cnt[3][xx]++;
					vis[2][xx][yy]=true;
					if(cnt[2][xx]==cnt[3][xx]){
						cnt[3][xx]--;
						vis[2][xx][yy]=false;
						continue;
					}
					q.push(pos{xx,yy,2});
				}else{
					if(vis[flag][xx][yy]||mp[xx][yy]=='#'){
						continue;
					}
					vis[flag][xx][yy]=true;
					q.push(pos{xx,yy,flag});
				}
			}
		}
		if(!brk){
			cout<<"No";
		}
		cout<<endl;
	}
}
2023/1/1 08:06
加载中...