文章

17

粉丝

166

获赞

6

访问

143.2k

头像
BFS
P1563 天津大学/南开大学2019年机试题
发布于2021年2月23日 14:20
阅读数 7.7k

#include <bits/stdc++.h>

using namespace std;

#define x	first
#define y	second

const int N = 100 + 5;
typedef pair<int, int> PII;
char g[N][N];
int d[N][N];
int dx[4] = {-1,0,1,0}, dy[4] = {0,-1,0,1};
int h, m;

int bfs(int sx, int sy)
{
	queue<PII> q;
	d[sx][sy] = 0;
	q.push({sx, sy});
	
	while(q.size())
	{
		auto t = q.front();
		q.pop();
		
		if(g[t.x][t.y] == 'E')
		{
			return d[t.x][t.y];
		}
		
		for(int i = 0; i < 4; i++)
		{
			int x = t.x + dx[i], y = t.y + dy[i];
			if((g[x][y] == '*' || g[x][y] == 'E') && d[x][y] == -1)
			{
				d[x][y] = d[t.x][t.y] + 1;
				q.push({x, y});
			}
		}
	}
	return -1;
}

int main()
{

	while(cin >> h >> m)
	{
	    int sx = 0, sy = 0;
		if(h == 0 && m == 0) break;
		memset(d, -1, sizeof d);
		memset(g, 0, sizeof g);
		for(int i = 0; i < h; i++)
		{
			cin >> g[i];
			for(int j = 0; j < m; j++)
				if(g[i][j] == 'S') sx = ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发