Last active
December 31, 2015 12:02
-
-
Save feugy/a49367159888dbfb2a1c to your computer and use it in GitHub Desktop.
Solution for coding game "Surface" - https://www.codingame.com/games/puzzles/31 (flooding, perf optimization)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| let [width, height] = [+readline(), +readline()] | |
| let n = height | |
| let grid = [] | |
| // use a boolean grid to make comparison faster | |
| while(n--) { | |
| // O is water and thus true. false is land | |
| grid.push(readline().split('').map(c => c === 'O')) | |
| } | |
| n = +readline() | |
| let points = [] | |
| while(n--) { | |
| let [x, y] = readline().split(' ').map(n => +n) | |
| points.push({x: x, y: y}) | |
| } | |
| /** | |
| * Explore grid from a given point and find lake containing it, if any. | |
| * (simple flood algorithm) | |
| * Performs repainting, that is, modifies the grid content | |
| * | |
| * @param {Object} start - starting coordinate | |
| * @param {Array<Array<String>>} grid - grid representing the surface | |
| * @return {Array<Object>} an array (that may be empty) of points in the lake | |
| */ | |
| const explore = (start, grid, height, width) => { | |
| const lake = [] | |
| const stack = [start] | |
| const maxHeight = grid.length - 2 | |
| const maxWidth = grid[0].length - 2 | |
| let i = 0 | |
| while(i < stack.length) { | |
| // do not remove from stack: memory is not the problem, time is | |
| const point = stack[i++] | |
| // check the point nature: water or field | |
| if (grid[point.y][point.x]) { | |
| // "repaint", and keep the formated representatin of the point | |
| grid[point.y][point.x] = false | |
| lake.push(point) | |
| // do not check candidate nature now, will be faster to enqueue in stack | |
| if (point.y <= maxHeight) { | |
| // go south | |
| stack.push({x: point.x, y: point.y + 1}) | |
| } | |
| if (point.y >= 1) { | |
| // go north | |
| stack.push({x: point.x, y: point.y - 1}) | |
| } | |
| if (point.x <= maxWidth) { | |
| // go east | |
| stack.push({x: point.x + 1, y: point.y}) | |
| } | |
| if (point.x >= 1) { | |
| // go north | |
| stack.push({x: point.x - 1, y: point.y}) | |
| } | |
| } | |
| } | |
| return lake | |
| } | |
| const lakes = [] | |
| points.forEach(({x, y}) => { | |
| // no need to explore if the lake was already found ! | |
| // as we perform "repainting", further exploration will fails | |
| // without this "memory" | |
| let lake = lakes.find(lake => lake.find(p => p.x === x && p.y === y)) | |
| if (!lake) { | |
| // tries to find a lake | |
| lake = explore({x: x, y: y}, grid) | |
| if (lake.length) { | |
| // and keep it for further points | |
| lakes.push(lake) | |
| } | |
| } | |
| return print(lake.length) | |
| }) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment