求助WA
查看原帖
求助WA
457610
hanks_楼主2022/10/3 18:17
#include<bits/stdc++.h>

using namespace std;
struct node
{
	int x,y,step;
}s,c,g;
queue<node>q;
int n,m,k1,k,f=0,dx[]={0,0,1,-1},dy[]={1,-1,0,0};
char a[1001][1001];
bool vis[1001][1001];
int bfs(int sx,int sy,int ex,int ey)
{
	q.push((node){sx,sy,0});
	vis[sx][sy]=1;
	while(!q.empty())
	{
		node u=q.front();
		q.pop();
		node v;
		v.step=u.step+1;
		for(int i=0;i<4;i++)
		{
			v.x=u.x+dx[i],v.y=u.y+dy[i];
			if(v.x>=n||v.y>=m||v.x<0||v.y<0||a[v.x][v.y]=='#'||vis[v.x][v.y])continue;
		
		
			q.push(v);
		
			vis[v.x][v.y]=1;
			if(v.x==ex&&v.y==ey){
				
				f=v.step;
				
				break;
			}
			
		}
		if(f>0)break; 
	}
	return f;
 } 
int main()
{
	
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)
		scanf("%s",a[i]);
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
	{
		if(a[i][j]=='S')
		s.x=i,s.y=j,s.step=0;
		if(a[i][j]=='C')
		c.x=i,c.y=j;
		
		if((s.x||s.y)&&(c.x||c.y)){k=bfs(s.x,s.y,c.x,c.y);break;} 
	}
	f=0;
	for(int i=0;i<n;i++)for(int j=0;j<m;j++)vis[i][j]=0;
	while(!q.empty())q.pop();
	
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
	{
		
		if(a[i][j]=='G')
		g.x=i,g.y=j;
		c.step=0;
		if((g.x||g.y)&&(c.x||c.y)){k1=bfs(c.x,c.y,g.x,g.y);break;} 
	}
	printf("%d\n",(k1==0||k==01?-1:k1+k));
 	return 0;
}



2022/10/3 18:17
加载中...