UVa 532 - Dungeon Master

  题目大意:给一个三维迷宫,给出入口和出口,找出最短路径。

  无权图上的单源最短路问题,使用BFS解决。

 #include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
#define MAXN 35 const int dir[][] = {{-, }, {, -}, {, }, {, }, {-, }};
int G[MAXN][MAXN][MAXN], dist[MAXN*MAXN*MAXN];
int L, R, C;
int s, e; int bfs()
{
queue<int> q;
memset(dist, -, sizeof(dist));
q.push(s);
dist[s] = ;
while (!q.empty())
{
int u = q.front();
q.pop();
int l = u / (R*C);
int r = (u%(R*C)) / C;
int c = (u%(R*C)) % C;
for (int i = ; i < ; i++)
{
int rr = r + dir[i][];
int cc = c + dir[i][];
int v = l*(R*C) + rr*C + cc;
if (rr >= && rr < R && cc >= && cc < C && G[l][rr][cc] && dist[v] == -)
{
q.push(v);
dist[v] = dist[u] + ;
if (v == e) return dist[e];
}
}
for (int i = ; i < ; i++)
{
int ll = l + dir[][i];
int v = ll*(R*C) + r*C + c;
if (ll >= && ll < L && G[ll][r][c] && dist[v] == -)
{
q.push(v);
dist[v] = dist[u] + ;
if (v == e) return dist[e];
}
}
}
return dist[e];
} int main()
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
char str[];
while (scanf("%d%d%d", &L, &R, &C) && (L || R || C))
{
getchar();
for (int k = ; k < L; k++)
{
for (int i = ; i < R; i++)
{
gets(str);
for (int j = ; j < C; j++)
{
if (str[j] == '.') G[k][i][j] = ;
else if (str[j] == '#') G[k][i][j] = ;
else if (str[j] == 'S')
{
s = k*(R*C) + i*C + j;
G[k][i][j] = ;
}
else if (str[j] == 'E')
{
e = k*(R*C) + i*C + j;
G[k][i][j] = ;
}
}
}
gets(str);
}
int ans = bfs();
if (ans > ) printf("Escaped in %d minute(s).\n", ans);
else if (ans == -) printf("Trapped!\n");
}
return ;
}
上一篇:数据仓库知识点梳理(3)


下一篇:语义分割的评价指标(OA, F1 score)计算(不使用sklearn)