UVa 10653 - Bombs! NO they are Mines!!

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

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

 #include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
#define MAXN 1100 int G[MAXN][MAXN], dist[MAXN*MAXN];
const int dir[][] = {{-, }, {, -}, {, }, {, }}; int main()
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
int R, C;
while (scanf("%d%d", &R, &C) && (R || C))
{
int k;
scanf("%d", &k);
memset(G, , sizeof G);
for (int i = ; i < k; i++)
{
int r, n;
scanf("%d%d", &r, &n);
for (int j = ; j < n; j++)
{
int x;
scanf("%d", &x);
G[r][x] = ;
}
}
int x, y;
scanf("%d%d", &x, &y);
int src = x*C + y;
scanf("%d%d", &x, &y);
int dest = x*C + y;
queue<int> q;
memset(dist, -, sizeof dist);
q.push(src);
dist[src] = ;
while (!q.empty())
{
int u = q.front();
q.pop();
if (u == dest) break;
int x = u / C;
int y = u % C;
for (int i = ; i < ; i++)
{
int dx = x + dir[i][], dy = y + dir[i][];
int v = dx * C + dy;
if (dx >= && dx < R && dy >= && dy < C && G[dx][dy] == && dist[v] == -)
{
dist[v] = dist[u] + ;
q.push(v);
}
}
}
printf("%d\n", dist[dest]);
}
return ;
}
上一篇:SuperSocket入门(五)-常用协议实现模版及FixedSizeReceiveFilter示例


下一篇:Apache多站点配置(ubuntu)(原创)