|
|
題目大意： 一個杯具男在地上躲隕石。用坐標軸的第一象限表示他的位置。 初始時刻他位于坐標軸原點。單位時間內(nèi)他只能移動一格。 有很多塊隕石在不同時刻砸下來，隕石砸的時候會把上下左右和中間的格子砸壞。 格子一旦砸壞了就不能再經(jīng)過了。 問，杯具男要怎么走才能在最短時間內(nèi)走到一個安全地點---隕石不會落下的地方。 思路： BFS搜索。如果走到某個地方，發(fā)現(xiàn)隕石已經(jīng)掉下來了，就不繼續(xù)走了。很常規(guī)的思路，呵呵。 代碼速度還行。根據(jù)排行來看~ 注意： Disscuss里有人說，此題數(shù)組要開到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;
}
|