87分过了14个数据,调不出来,感谢大神求助
查看原帖
87分过了14个数据,调不出来,感谢大神求助
792453
iamfbb楼主2023/3/22 22:05

调不出来,不知道问题在哪里

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define x first
#define y second
typedef pair<int,int>PII;
vector<PII>a[30];
const int N=305;
int n,m;
int x1,y1,x2,y2;
int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int dist[N][N];
char s[N][N];
bool st[N][N];
void bfs(int x,int y)
{
	queue<PII>q;
	q.push({x,y});
	st[x][y]=1;
	while(!q.empty())
	{
		PII t=q.front();
		q.pop();
		if(t.x==x2&&t.y==y2)break;
		for(int i=0;i<4;i++)
		{
			int nx=t.x+d[i][0],ny=t.y+d[i][1];
			if(nx<0||nx>=n||ny<0||ny>=m||s[nx][ny]=='#'||st[nx][ny])continue;
			if(s[nx][ny]>='A'&&s[nx][ny]<='Z'){
				int ver=s[nx][ny]-65;
				for(int i=0;i<a[ver].size();i++)
				{
					auto r=a[ver][i];
					if(r.x==nx&&r.y==ny)continue;
					dist[r.x][r.y]=dist[t.x][t.y]+1;
					q.push({r.x,r.y});
					break;
				}
			}
			else{
				dist[nx][ny]=dist[t.x][t.y]+1;
			    st[nx][ny]=1;
			    q.push({nx,ny});
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)scanf("%s",s[i]);
	for(int i=0;i<n;i++)
	   for(int j=0;j<m;j++)
	   {
	   	  if(s[i][j]=='@')x1=i,y1=j;
	   	  else if(s[i][j]=='=')x2=i,y2=j;
	   	  else if(s[i][j]>='A'&&s[i][j]<='Z'){
	   	  	int t=s[i][j]-65;
	   	  	a[t].push_back({i,j});
		  }
	   } 
	bfs(x1,y1);
	printf("%d",dist[x2][y2]);
	return 0;
}
2023/3/22 22:05
加载中...