求优化(TLE 0)
查看原帖
求优化(TLE 0)
1024529
sszxyyds楼主2024/5/31 15:24
#include<stdio.h>
#include<string.h>
char mp[4501][4501];
int t[4501][4501],vis[4501][4501];
int sl,sr;
int ix[4]={1,-1,0,0};
int iy[4]={0,0,1,-1};
int n,m,success=0;
struct node{
	int x,y;
}stac[6000009];
int top,hd;
void dfs(int x,int y){
	if(success==1){
		return ;
	}
	vis[x][y]=1;
	int rx,ry;
	for(int i=0;i<4;i++){
		rx=ix[i]+x;
		ry=iy[i]+y;
		if(mp[rx][ry]=='#'||mp[rx][ry]==NULL){
			continue;
		}
		if(vis[rx][ry]==0){
			if(mp[rx][ry]=='S'){
				success=1;return;
			}else if(mp[rx][ry]=='.'){
				dfs(rx,ry);
			}
		}
	}
}
int main(){
	while(scanf("%d%d",&n,&m)!=EOF){
		memset(vis,0,sizeof(vis));
		memset(mp,0,sizeof(mp));
		top=0;hd=0;success=0;
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				char c;
				scanf("%c",&c);
				if(c=='\n'){
					j--;
					continue;
				}
				mp[i+n][j+m]=c;
				mp[i][j+m]=c;
				mp[i+n][j]=c;
				mp[i+2*n][j+m]=c;
				mp[i+n][j+2*m]=c;
				if(c=='S'){
					sl=i+n,sr=j+m;
				}
			}
		}
		dfs(sl,sr);
		if(success==1){
			printf("Yes\n");	
		}else{
			printf("No\n");
		} 		
	}
	return 0;
}
2024/5/31 15:24
加载中...