Skip to content

Instantly share code, notes, and snippets.

@cazlu8
Last active July 12, 2022 18:01
Show Gist options
  • Save cazlu8/304aa44b5b90d6428bf2269ee96726d6 to your computer and use it in GitHub Desktop.
Save cazlu8/304aa44b5b90d6428bf2269ee96726d6 to your computer and use it in GitHub Desktop.
function filterValidLands(allPositions, landPositions){
return allPositions.length - landPositions.length;
}
function dfs(matrix, matrixR, matrixC, currentMove, visitedNodes, landPositions) {
const [x, y] = currentMove.shift();
const possibleMoves = [[x - 1, y],
[x, y -1],
[x + 1, y],
[x, y + 1]];
for(let i = 0; i < 4; i++){
const [moveX, moveY] = possibleMoves[i];
if(moveX >= 0 && moveX < matrixR && moveY >= moveY && moveY < matrixC) {
if (!visitedNodes[moveX][moveY]) {
visitedNodes[moveX][moveY] = true;
if(matrix[moveX][moveY] === 0)
continue;
if(matrix[moveX][moveY] === 1) {
landPositions.push(true)
dfs(matrix, matrixR, matrixC, [[moveX, moveY]], visitedNodes, landPositions)
}
}
}
}
}
function isOnTheBorder(matrixR, matrixC, x, y) {
return x === 0 || x === matrixR - 1 || y === 0 || y === matrixC - 1;
}
var numEnclaves = function(matrix) {
let allPositions = [];
let landPositions = [];
const matrixR = matrix.length;
const matrixC = matrix[0].length;
const visitedNodes = matrix.map(x => x.map(() => false));
for (let x = 0; x < matrixR; x++) {
for (let y = 0; y < matrixC; y++) {
if(matrix[x][y] === 0)
continue;
allPositions.push(true)
if (!visitedNodes[x][y] && isOnTheBorder(matrixR, matrixC, x, y)) {
visitedNodes[x][y] = true;
landPositions.push(false)
dfs(matrix, matrixR, matrixC, [[x, y]], visitedNodes, landPositions)
}
}
}
return filterValidLands(allPositions, landPositions)
}
console.log(numEnclaves(
[[0,0,0,1,1,1,0,1,0,0],[1,1,0,0,0,1,0,1,1,1],[0,0,0,1,1,1,0,1,0,0],[0,1,1,0,0,0,1,0,1,0],[0,1,1,1,1,1,0,0,1,0],[0,0,1,0,1,1,1,1,0,1],[0,1,1,0,0,0,1,1,1,1],[0,0,1,0,0,1,0,1,0,1],[1,0,1,0,1,1,0,0,0,0],[0,0,0,0,1,1,0,0,0,1]]));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment