Goal
After years of searching, you have finally found the Holy Grail in a room of size W x Hwith W being the width and H the height.You can see the grail in the far corner of the room, but there is a large chasm between your position and the Grail's position. Every several seconds a tile appears, hovering over the chasm.
At first, there are only 2 hovering tiles: one in position (0,0) where your bot is located, and one in position (W-1, H-1) where the Grail is resting. Your bot can only move horizontally or vertically between visible tiles.
Your task is to detect when a complete path has been created for your bot to get to the Holy Grail. Once the complete path is revealed, your bot must immediately sprint the entire distance from his current location to the tile containing the Holy Grail. If you send him too early, he will fall into the pit. Too late, and the Holy Grail will have disappeared.
Next ? lines: Two space separated integers tileX and tileY for the coordinates of a new tile.
2 ≤ H ≤ 40
0 ≤ tileX < W
0 ≤ tileY < H
Solution
For each iteration we get a new tile at an arbitrary position. It's not said that it will connect to previous tiles and we need to figure out when a path from the start position \((0, 0)\) to the position of the grail at \((w-1, h-1)\) is closed. To keep track of the tiles, we span a grid map of size \(w\times h\) in a two dimensional array and mark every new tile we get in the map. For each such new tile we need an algorithm to check if a path exists:
var [W, H] = readline().split(' ').map(Number);
var n = 0;
// Create a grid map
var map = new Array(H);
for (var i = 0; i < map.length; i++) {
map[i] = new Array(W);
}
// Mark start and end
map[0][0] = true;
map[H - 1][W - 1] = true;
while (inputs = readline()) {
var [tileX, tileY] = inputs.split(' ').map(Number);
// Mark new tile and increment the loop count
map[tileY][tileX] = true;
n++;
// Check if path exist and break free
if (pathExists(map, 0, 0, W - 1, H - 1, {})) {
print(n);
break;
}
} All that is still needed is a routine to check if a path from start to end exists. This can be done with a graph exploration algorithm like depth first search (DFS) or breadth first search (BFS), by seeing the grid as a partially connected graph. As soon as two tiles are next to each other, we see it as neighbors on the graph. Since we want to progress as fast as possible to find a connection on the graph, a DFS is the better option. Implementing it is pretty straight forward; we recursively try to go in all four directions from a tile, as long as we're not off grid and haven't visited the tile already:
function pathExists(map, sx, sy, dx, dy, visited) {
if (sx == dx && sy == dy) {
return true;
}
visited[sx + ',' + sy] = true;
var dir = [{x: 0, y: 1}, {x: 1, y: 0}, {x: 0, y: -1}, {x: -1, y: 0}];
for (var i = 0; i < dir.length; i++) {
var x = sx + dir[i].x;
var y = sy + dir[i].y;
if (0 <= x && x <= dx && 0 <= y && y <= dy && map[y][x] && !visited[x + ',' + y]) {
if (pathExists(map, x, y, dx, dy, visited)) return true;
}
}
return false;
}