文章
105
粉丝
69
获赞
117
访问
56.8k
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int n, m;
char g[N][N]; //存图
int d[N][N]; //存每个点最短距离
//四个方向偏移量
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
//bfs宽搜
int bfs(int x1, int y1)
{
queue<PII> q; //pair数据类型的队列
d[x1][y1] = 0;//初始化起点为0
q.push({x1, y1}); //存起点的坐标
while(q.size())
{
auto t = q.front();
q.pop(); //搜完每个点注意弹出
int a = t.first, b = t.second;
for(int i = 0; i < 4; i ++) //枚举四个方向
{
int x = a + dx[i], y = b + dy[i];
if(g[x][y] == 'E') return d[a][b] + 1; //搜到终点直接返回答案
//边界和搜索条件
if(x > 0 && y > 0 && x <= n && y <= m && d[x][y] == -1 && g[x][y] == '*')
{
d[x][y] = d[a][b] + 1; //更新*到S距离
q.push({x, y}); //将上下左右扩展的*的坐标加入队列中
}
}
}
return -1; //没搜到E就返回-1
}
int main()
{
while(cin >> n >> m, n, m)
{
memset(d, -1, sizeof d); //每次数据距离初始...
登录后发布评论
暂无评论,来抢沙发