Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created April 17, 2016 02:22
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/eed134d2642090603865a44009d1e67a to your computer and use it in GitHub Desktop.
Save jianminchen/eed134d2642090603865a44009d1e67a to your computer and use it in GitHub Desktop.
Connected Cell in a grid - JavaScript code
function processData(input) {
var lines = input.split('\n');
var height = parseFloat(input[0]);
var width = parseFloat(input[1]);
lines.splice(0, 2);
var matrix = lines.map(function(line) {
return line.split(' ').map(parseFloat);
});
var visited = lines.map(function(line) {
return [];
});
var largest = 0, largestCells, current, cells;
var directions = [
{ x: -1, y: -1 }, // top left
{ x: 0, y: -1 }, // top
{ x: 1, y: -1 }, // top right
{ x: 1, y: 0 }, // right
{ x: 1, y: 1 }, // bottom right
{ x: 0, y: 1 }, // bottom
{ x: -1, y: 1 }, // bottom left
{ x: -1, y: 0 }, // left
];
function dfs(x, y) {
if (x < 0 || y < 0 || x >= width || y >= height || visited[y][x]) return 0;
visited[y][x] = true;
if (!matrix[y][x]) return 0;
cells.push({
x: x,
y: y,
});
return directions.reduce(function(acc, direction) {
return acc + dfs(x + direction.x, y + direction.y);
}, 1);
}
matrix.forEach(function(row, y) {
row.forEach(function(val, x) {
if (visited[y][x]) return;
current = 0;
cells = [];
var area = dfs(x, y);
if (area > largest) {
largest = area;
largestCells = cells;
}
});
})
console.log(largest);
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment