priority_queue的bfs
priority_queue的bfs相当于使用了dijkstra的思想。 View Code
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
using namespace std;
#define maxn 305
struct Point
{
int x, y, w;
}s, t;
int n, m;
char map[maxn][maxn];
bool vis[maxn][maxn];
int dir[4][2] = {
{
1,0},{-1,0},{
0,1},{
0,-1}};
bool operator < (const Point &a, const Point &b)
{
return a.w > b.w;
}
void input()
{
for (int i = 0; i < n; i++)
scanf("%s", map[i]);
}
void work()
{
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
if (map[i][j] == 'Y')
{
s.x = i;
s.y = j;
s.w = 0;
map[i][j] = 'E';
}
if (map[i][j] == 'T')
{
t.x = i;
t.y = j;
map[i][j] = 'E';
}
}
}
bool ok(Point a, int &step)
{
if (a.x < 0 || a.y < 0 || a.x >= n || a.y >= m)
return false;
if (vis[a.x][a.y])
return false;
if (map[a.x][a.y] == 'S' ||map[a.x][a.y] == 'R')
return false;
if (map[a.x][a.y] == 'E')
{
step = 1;
return true;
}
step = 2;
return true;
}
int bfs()
{
priority_queue <Point> pq;
memset(vis, 0, sizeof(vis));
pq.push(s);
vis[s.x][s.y] = true;
while (!pq.empty())
{
Point u = pq.top();
pq.pop();
if (u.x == t.x && u.y == t.y)
return u.w;
Point v;
for (int i = 0; i < 4; i++)
{
v.x = u.x + dir[i][0];
v.y = u.y + dir[i][1];
int step;
if (ok(v, step))
{
v.w = u.w + step;
pq.push(v);
vis[v.x][v.y] = true;
}
}
}
return -1;
}
int main()
{
//freopen("t.txt", "r", stdin);
while (scanf("%d%d", &n, &m), n | m)
{
input();
work();
printf("%d\n", bfs());
}
return 0;
}
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/110368.html原文链接:https://javaforall.cn