Skip to content

Instantly share code, notes, and snippets.

@reyou
Created May 24, 2018 02:25
Show Gist options
  • Save reyou/203537b23b38425212f45b50c0f4a8a3 to your computer and use it in GitHub Desktop.
Save reyou/203537b23b38425212f45b50c0f4a8a3 to your computer and use it in GitHub Desktop.
/** Algorithm: given a collection (matrix) of
pixels you must find the size of the largest shape.
Shapes were defined as pixels touching each other orthogonality. */
var input = [
[1, 1, 1, 1, 0],
[1, 1, 0, 1, 0],
[1, 1, 0, 0, 0],
[0, 0, 0, 0, 0]
];
var input2 = [
[1, 1, 0, 0, 0],
[1, 1, 0, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 0, 1, 1]
];
console.log(findMax(input));
console.log(findMax(input2));
function findMax(input) {
var count = 0;
let rowCount = input.length;
let colCount = input[0].length;
for (let i = 0; i < rowCount; i++) {
for (let j = 0; j < colCount; j++) {
var currentCount = search(input, i, j, 0);
if (currentCount > count) {
count = currentCount;
}
}
}
return count;
}
function search(input, row, col, counter) {
if (
row < 0 ||
col < 0 ||
row > input.length - 1 ||
col > input[0].length - 1 ||
input[row][col] === 0
) {
return counter;
} else {
input[row][col] = 0;
counter = counter + 1;
}
// top, right, bottom, left
counter = search(input, row - 1, col, counter);
counter = search(input, row, col + 1, counter);
counter = search(input, row + 1, col, counter);
counter = search(input, row, col - 1, counter);
return counter;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment