-
-
Save rkumorek/b12414b80b956d1122f1e9a46927fbe2 to your computer and use it in GitHub Desktop.
find size of largest region in matrix... solutions are breadth-first iterative (2) and depth-first recursive (3)
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
| // Adapted from: https://www.geeksforgeeks.org/find-length-largest-region-boolean-matrix/ | |
| "use strict"; | |
| var M1 = [ | |
| [ 0, 0, 1, 1, 0 ], | |
| [ 1, 0, 1, 1, 0 ], | |
| [ 0, 1, 0, 0, 0 ], | |
| [ 0, 0, 0, 1, 1 ] | |
| ]; | |
| console.log( | |
| findMaxRegionArea(M1) // 6 | |
| ); |
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
| // iterative breadth-first solution | |
| function findMaxRegionArea(matr) { | |
| const ROW_LEN = matr[0].length; | |
| var area = 0; | |
| var maxArea = 0; | |
| var visited = new Set(); | |
| for (let [ rowIdx, row ] of matr.entries()) { | |
| for (let [ colIdx, cell ] of row.entries()) { | |
| if ( | |
| !visited.has((rowIdx * ROW_LEN) + colIdx) && | |
| cell == 1 | |
| ) { | |
| // initialize a breadth-first queue | |
| let toVisit = [ [rowIdx, colIdx] ]; | |
| while (toVisit.length > 0) { | |
| // pull to-visit cell coordinates off the queue | |
| let [ visitedRowIdx, visitedColIdx ] = toVisit.shift(); | |
| // compute the cell-index | |
| let visitedCellIdx = (visitedRowIdx * ROW_LEN) + visitedColIdx; | |
| // have we not visited this cell yet? | |
| if (!visited.has(visitedCellIdx)) { | |
| visited.add(visitedCellIdx); | |
| area++; | |
| // inspect current row and two (possibly) adjacent rows | |
| for (let rowDelta of [ -1, 0, 1 ]) { | |
| // inspect current column and two (possibly) adjacent columns | |
| for (let colDelta of [ -1, 0, 1 ]) { | |
| // avoid re-considering the current cell | |
| if (!(rowDelta == 0 && colDelta == 0)) { | |
| let toVisitRowIdx = (visitedRowIdx + rowDelta); | |
| let toVisitColIdx = (visitedColIdx + colDelta); | |
| // is the cell actually in bounds of the matrix, | |
| // and is has a `1` in it, and is not already | |
| // a cell we've visited/counted? | |
| if ( | |
| toVisitRowIdx >= 0 && | |
| toVisitRowIdx <= (matr.length - 1) && | |
| toVisitColIdx >= 0 && | |
| toVisitColIdx <= (ROW_LEN - 1) && | |
| matr[toVisitRowIdx][toVisitColIdx] == 1 && | |
| !visited.has((toVisitRowIdx * ROW_LEN) + toVisitColIdx) | |
| ) { | |
| // schedule visiting this adjacent cell via | |
| // the (breadth-first) queue | |
| toVisit.push([ toVisitRowIdx, toVisitColIdx ]); | |
| } | |
| } | |
| } | |
| } | |
| } | |
| } | |
| // did this region have a bigger area than | |
| // we've seen so far? | |
| if (area > maxArea) { | |
| maxArea = area; | |
| } | |
| area = 0; | |
| } | |
| } | |
| } | |
| return maxArea; | |
| } |
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
| // recursive depth-first solution | |
| function findMaxRegionArea(matr) { | |
| const ROW_LEN = matr[0].length; | |
| var maxArea = 0; | |
| var visited = new Set(); | |
| for (let [ rowIdx, row ] of matr.entries()) { | |
| for (let [ colIdx, cell ] of row.entries()) { | |
| if ( | |
| !visited.has((rowIdx * ROW_LEN) + colIdx) && | |
| cell == 1 | |
| ) { | |
| let area = ( | |
| 1 + countAdjacentArea( | |
| rowIdx, | |
| colIdx, | |
| visited, | |
| ROW_LEN, | |
| matr | |
| ) | |
| ); | |
| // did this region have a bigger area than | |
| // we've seen so far? | |
| if (area > maxArea) { | |
| maxArea = area; | |
| } | |
| } | |
| } | |
| } | |
| return maxArea; | |
| } | |
| function countAdjacentArea(visitedRowIdx,visitedColIdx,visited,ROW_LEN,matr) { | |
| var area = 0; | |
| // compute the cell-index | |
| var visitedCellIdx = (visitedRowIdx * ROW_LEN) + visitedColIdx; | |
| // have we not visited this cell yet? | |
| if (!visited.has(visitedCellIdx)) { | |
| visited.add(visitedCellIdx); | |
| // inspect current row and two (possibly) adjacent rows | |
| for (let rowDelta of [ -1, 0, 1 ]) { | |
| // inspect current column and two (possibly) adjacent columns | |
| for (let colDelta of [ -1, 0, 1 ]) { | |
| // avoid re-considering the current cell | |
| if (!(rowDelta == 0 && colDelta == 0)) { | |
| let toVisitRowIdx = (visitedRowIdx + rowDelta); | |
| let toVisitColIdx = (visitedColIdx + colDelta); | |
| // is the cell actually in bounds of the matrix, | |
| // and is has a `1` in it, and is not already | |
| // a cell we've visited/counted? | |
| if ( | |
| toVisitRowIdx >= 0 && | |
| toVisitRowIdx <= (matr.length - 1) && | |
| toVisitColIdx >= 0 && | |
| toVisitColIdx <= (ROW_LEN - 1) && | |
| matr[toVisitRowIdx][toVisitColIdx] == 1 && | |
| !visited.has((toVisitRowIdx * ROW_LEN) + toVisitColIdx) | |
| ) { | |
| // recursively (depth-first) visit all this | |
| // cell's unvisited adjacent cells to find | |
| // the whole region | |
| area += ( | |
| 1 + countAdjacentArea( | |
| toVisitRowIdx, | |
| toVisitColIdx, | |
| visited, | |
| ROW_LEN, | |
| matr | |
| ) | |
| ); | |
| } | |
| } | |
| } | |
| } | |
| } | |
| return area; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment