文章

218

粉丝

0

获赞

872

访问

32.6k

头像
迷宫 题解:
P1563 天津大学/南开大学机试题
发布于2026年1月31日 22:07
阅读数 201

#include<iostream>
#include<cstring>
#include<queue>
#define x first
#define y second

using namespace std;

const int N=110;

int h,w;
char g[N][N];
int d[N][N];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int x0,y0;

int bfs()
{
	queue<pair<int,int>> q;
	q.push({x0,y0});
	d[x0][y0]=0;
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
			int a=t.x+dx[i],b=t.y+dy[i];
			if(a<0||a>=h||b<0||b>=w)
				continue;
			if(g[a][b]=='#')
				continue;
			if(d[a][b]!=-1)
				continue;
			d[a][b]=d[t.x][t.y]+1;
			q.push({a,b});
			if(g[a][b]=='E')
				return d[a][b];
		}
	}
	return -1;
}

int main()
{
	while(cin>>h>>w)
	{
		if(h==0&&w==0)
			break;
		memset(d,-1,sizeof d);
		for(int i=0;i<h;i++)
			for(int j=0;j<w;j++)
			{
				cin>>g[i][j];
				if(g[i][j]=='S')
				{
					x0=i;
					y0=j;
				}
			}
		cout<<bfs()<<endl;
...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发