|
|
题目大意： 一个杯具男在地上躲陨石。用坐标轴的第一象限表示他的位置。 初始时刻他位于坐标轴原点。单位时间内他只能移动一格。 有很多块陨石在不同时刻砸下来，陨石砸的时候会把上下左右和中间的格子砸坏。 格子一旦砸坏了就不能再经过了。 问，杯具男要怎么走才能在最短时间内走到一个安全地点---陨石不会落下的地方。 思路： BFS搜索。如果走到某个地方，发现陨石已经掉下来了，就不继续走了。很常规的思路，呵呵。 代码速度还行。根据排行来看~ 注意： Disscuss里有人说，此题数组要开到400。
 #include <stdio.h>
int map[450][450];
char visited[450][450];
  struct node  {
  struct {
 int x, y;
 } arr[8192];
int cnt;
 } _queue[2], *cur, *nxt;
__inline int in_range(int x, int y)
{
return !(x < 0 || y < 0);
}
__inline void insert(struct node *n, int x, int y)
{
if (!in_range(x, y) || visited[x][y])
return ;
n->arr[n->cnt].x = x;
n->arr[n->cnt].y = y;
visited[x][y] = 1;
n->cnt++;
}
__inline void crash(int x, int y, int t)
{
if (!in_range(x, y))
return ;
if (!map[x][y] || t + 1 < map[x][y])
map[x][y] = t + 1;
}
int solve()
{
int x, y, step, i, t;
_queue[0].cnt = 1;
visited[0][0] = 1;
for (step = 0; ; step++) {
cur = &_queue[step & 1];
nxt = &_queue[(step + 1) & 1];
if (!cur->cnt)
return -1;
nxt->cnt = 0;
for (i = 0; i < cur->cnt; i++) {
x = cur->arr[i].x;
y = cur->arr[i].y;
t = map[x][y];
if (!t) {
//printf("step %d (%d,%d) %d\n", step, x, y, t);
return step;
}
if (step + 1 >= t)
continue;
//printf("step %d (%d,%d) %d\n", step, x, y, t);
insert(nxt, x - 1, y);
insert(nxt, x + 1, y);
insert(nxt, x, y + 1);
insert(nxt, x, y - 1);
}
}
}
int main()
{
int m, x, y, t;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d", &m);
while (m--) {
scanf("%d%d%d", &x, &y, &t);
crash(x, y, t);
crash(x + 1, y, t);
crash(x - 1, y, t);
crash(x, y + 1, t);
crash(x, y - 1, t);
}
printf("%d\n", solve());
return 0;
}
|