Goal of this puzzle is to found pirate's treasure.
Input
Line 1: Width W of treasure map.
Line 2: Height H of treasure map.
Next H lines:W symbols (0 or 1) indicating free space (0) or obstacle (1).
Treasure is placed on free space surrounded by only obstacles.
There are three possibilities how can be the treasure surrounded:
By 3 obstacles when the treasure is in the corner of the map.
By 5 obstacles when the treasure is on the edge of the map.
By 8 obstacles when the treasure is inside the map.
Line 2: Height H of treasure map.
Next H lines:W symbols (0 or 1) indicating free space (0) or obstacle (1).
Treasure is placed on free space surrounded by only obstacles.
There are three possibilities how can be the treasure surrounded:
By 3 obstacles when the treasure is in the corner of the map.
By 5 obstacles when the treasure is on the edge of the map.
By 8 obstacles when the treasure is inside the map.
Output
Coordinates of treasure in map represented by indexes separated by space. For example: "12 5"
Position "0 0" is in the top left corner, so maximum index x is W-1 and maximum index y is H-1.
Position "0 0" is in the top left corner, so maximum index x is W-1 and maximum index y is H-1.
Constraints
* 2 <= W <= 25
* 2 <= H <= 25
* Only 1 treasure in map.
* 2 <= H <= 25
* Only 1 treasure in map.
Solution
Imagine we take a stamp of size 3x3 and move the center cell over the whole grid. If the center element is not zero we can skip immediately. Otherwise we test every single cell around the center cell. If the cell does not exist, because we are at a wall, we assume an obstacle which simplifies the code a bit. The implementation of this idea then is
const W = +readline();
const H = +readline();
const map = [];
for (let i = 0; i < H; i++) {
map.push(readline().split(' ').map(Number));
}
const getCell = (row, col) =>
(map[row] === undefined || map[row][col] === undefined) ? 1 : map[row][col];
function solution(map) {
for (let i = 0; i < map.length; i++) {
for (let j = 0; j < map[i].length; j++) {
if (map[i][j] === 0
&& getCell(i - 1, j - 1)
&& getCell(i - 1, j)
&& getCell(i - 1, j + 1)
&& getCell(i, j - 1)
// i,j == 0
&& getCell(i, j + 1)
&& getCell(i + 1, j - 1)
&& getCell(i + 1, j)
&& getCell(i + 1, j + 1)) {
print(j, i);
return;
}
}
}
}
solution(map);