46分,不知道哪里错了,jiujiuwo
查看原帖
46分,不知道哪里错了,jiujiuwo
112375
1a2b3楼主2022/10/27 13:53
#include <bits/stdc++.h>
using namespace std;
struct cs{
	int x[10];//门的x坐标 
	int y[10];//门的y坐标 
	int s=1;//门的编号 
}men[2000];
struct que{
	int x,y,s;//x,y是坐标,s是步数 
}u;
queue<que>shu;
int n,m,x,y,zx,zy,a[20]={0,0,-1,1},b[20]={1,-1,0,0},vis[500][500];//vis存图 
char p[500][500];//输入的字符 
int menfanhui(int x,int y,char str)//返回终点门的编号 
{
	for(int i=1;i<=2;i++)
	{
		if(men[str].x[i]!=x&&men[str].y[i]!=y)
		{
//			cout<<men[str].x[i]<<" "<<men[str].y[i]<<endl;
			return i;
		}
	}
}
void bfs()
{
	while(!shu.empty())
	{
		que d=shu.front(),h;
		for(int i=0;i<4;i++)//四个方向 
		{
			h.x=d.x+a[i];
			h.y=d.y+b[i];
			h.s=d.s+1;
			if(h.x==zx&&h.y==zy)//终点了输出,返回 
			{
				cout<<h.s;
				return ;
			}
			if(h.x>0&&h.x<=n&&h.y>0&&h.y<=m)//判断有没有超出边界 
			{
				if(p[h.x][h.y]>='A'&&p[h.x][h.y]<='Z'&&vis[h.x][h.y]==0)//是否是门 
				{
//					cout<<p[h.x][h.y]<<" "<<endl;
					int menf=menfanhui(h.x,h.y,p[h.x][h.y]),ano;//找到终点门的编号 
					if(menf==1)ano=2;//找到初始门的编号 
					if(menf==2)ano=1;
					char cun=p[h.x][h.y];//为了方便 
					vis[h.x][h.y]=1;//标记初始门 
					h.x=men[cun].x[menf];//下一个点应该是终点门 
					h.y=men[cun].y[menf];
					shu.push(h);//终点门入队 
				}
				if(p[h.x][h.y]=='.'&&vis[h.x][h.y]==0)//普通走路 
				{
					vis[h.x][h.y]=1;
					shu.push(h);
				}
			}
		}
		shu.pop();//找过的点出队 
	}
	return ;
}
int main()
{
	memset(p,0,sizeof(p));
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>p[i][j];//输入点 
			if(p[i][j]=='@')x=i,y=j;//存初始点 
			if(p[i][j]>='A'&&p[i][j]<='Z')//找门 
			{
					men[p[i][j]].x[men[p[i][j]].s]=i;men[p[i][j]].y[men[p[i][j]].s]=j;//s是门的编号 
					men[p[i][j]].s++;//编号加一,保证存到两个门 
			}
			if(p[i][j]=='=')zx=i,zy=j;//存终点值 
			if(p[i][j]=='#')vis[i][j]=-1;//不能走就存-1 
		}
	}
	vis[x][y]=1;//初始点不能走 
	u.x=x;u.y=y;//s默认为0, 
	shu.push(u);//起点入队 
	bfs();
	return 0;
 } 
2022/10/27 13:53
加载中...