[蒟蒻求助]改了2个小时了还不对
查看原帖
[蒟蒻求助]改了2个小时了还不对
526518
respect_lowsmile楼主2022/4/17 14:43
#include<iostream>
#include<queue>
using namespace std;
int n,m,sx,sy,fx,fy;
char map[301][301];
int vis[301][301];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
struct point 
{
	int x,y,step;
};
point en,now;
queue<point> q;
void tp(int x,int y)
{
	for(int i=1;i<=n;++i)
	  {
	  	for(int j=1;j<=m;++j)
	  	  {
	  	  	if((map[i][j]==map[x][y])&&(x!=i||y!=j))
	  	  	  {
	  	  	    en.x=i;
	  	  	    en.y=j;
	  	  	    return ;
			  }
		  }
	  }
}
void bfs()
{
	now.x=sx,now.y=sy,now.step=0;
	vis[sx][sy]=1;
	q.push(now);
	while(!q.empty())
	{
		now=q.front();
		q.pop();
		for(int i=0;i<4;++i)
		  {
		  	en.x=now.x+dx[i];
		  	en.y=now.y+dy[i];
		  	if(en.x>=1&&en.y>=1&&en.x<=n&&en.y<=n&&vis[en.x][en.y]==0&&map[en.x][en.y]!='#')
		  	  {
				if(map[en.x][en.y]>='A'&&map[en.x][en.y]<='Z') vis[en.x][en.y]=0;
		  	    else vis[en.x][en.y]=1;
				en.step=now.step+1;
				if(map[en.x][en.y]>='A'&&map[en.x][en.y]<='Z')
		  	  	  {
					tp(en.x,en.y);
				  }
		  	  	if(en.x==fx&&en.y==fy)
		  	  	  { 
		  	  	  	printf("%d",en.step);
					return ; 
				  }
		  	  	q.push(en);
			  }
		  }
	}
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i)
	  {
	  	for(int j=1;j<=m;++j)
	  	  {
	  	  	scanf(" %c",&map[i][j]);
	  	  	if(map[i][j]=='@')  sx=i,sy=j;
			if(map[i][j]=='=')  fx=i,fy=j; 
		  }
	  }
	bfs();
	return 0;
}
2022/4/17 14:43
加载中...