Meteor Shower (POJ 3669)
Use breadth first search. Note that you need mark cells that has already been visited or it will exceed time limit. You'd better decide not adding a cell into the queue as soon as possible.
import java.io.*;
import java.util.*;
class Position{
int x;
int y;
public Position(int x, int y) {
this.x = x;
this.y = y;
}
}
public class MeteorShower {
static private int[] dx = {1, 0, -1, 0};
static private int[] dy = {0, 1, 0, -1};
private static void solve(int[][] ground) {
LinkedList<Position> queue = new LinkedList<Position>();
int time = 0;
queue.addLast(new Position(0, 0));
queue.addLast(null);
while (!queue.isEmpty()) {
Position p = queue.pollFirst();
if (p == null) {
time++;
if (!queue.isEmpty()) queue.addLast(null);
continue;
}
for (int i = 0; i < 4; i++) {
int nx = p.x + dx[i], ny = p.y + dy[i];
if (nx < 0 || ny < 0) continue;
if (ground[nx][ny] <= (time + 1)) continue;
if (ground[nx][ny] == Integer.MAX_VALUE) {
System.out.println(time + 1);
return;
}
queue.addLast(new Position(nx, ny));
ground[nx][ny] = 0;
}
}
System.out.println(-1);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int[][] ground = new int[305][305];
for (int i = 0; i < 305; i++) Arrays.fill(ground[i], Integer.MAX_VALUE);
for (int i = 0; i < N; i++) {
int x = in.nextInt(), y = in.nextInt(), t = in.nextInt();
ground[x][y] = Math.min(ground[x][y], t);
if (x > 0) ground[x - 1][y] = Math.min(ground[x - 1][y], t);
if (y > 0) ground[x][y - 1] = Math.min(ground[x][y - 1], t);
ground[x + 1][y] = Math.min(ground[x + 1][y], t);
ground[x][y + 1] = Math.min(ground[x][y + 1], t);
}
solve(ground);
}
}