25pts求助
查看原帖
25pts求助
823773
_sh1kong_楼主2022/11/29 09:45

CODE:

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;//corn_maze
int n,m,enx,eny,nx,ny;
char maze[310][310];
bool vis[310][310];
struct node{
	int x,y,step;
};
queue <node> q;
int pyx[5]={0,0,1,-1},
	pyy[5]={1,-1,0,0};
void find(int i,int j)
{
	for(int k=1;k<=n;k++)
	{
		for(int kk=1;kk<=m;kk++)
		{
			if(maze[k][kk]==maze[i][j])
			{
				nx=k,ny=kk;
				return ;
			}
		}
	}
} 
void bfs()
{
	int xx,yy;
	while(!q.empty())
	{
		node k=q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
			xx=k.x+pyx[i];yy=k.y+pyy[i];
			if(xx>=1&&yy>=1&&xx<=n&&yy<=m&&!vis[xx][yy])
			{
				if(maze[xx][yy]>='A'&&maze[xx][yy]<='Z')
				{
					find(xx,yy);
					vis[xx][yy]=vis[nx][ny]=1;
					node s;
					s.x=nx;s.y=ny;s.step=k.step+1;
					q.push(s);
				}
				else
				{
					vis[xx][yy]=1;
					node s;
					s.x=xx;s.y=yy;s.step=k.step+1;
					q.push(s);
				}
				if(q.back().x==enx&&q.back().y==eny)
				{
					printf("%d\n",q.back().step);
					exit(0);
				}
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			char ch;
			cin>>ch;
			if(ch=='#') vis[i][j]=1;
			else if(ch>='A'&&ch<='Z') maze[i][j]=ch;
			else if(ch=='@')
			{
				node p;
				p.x=i;p.y=j;p.step=0;
				q.push(p);
				vis[i][j]=1;
			}
			else if(ch=='=') enx=i,eny=j;
		}
	}
	bfs();
	return 0;
}
2022/11/29 09:45
加载中...