Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
- two step dfs approach, more efficient to do bfs similar to rotten oranges
Solution
varnumIslands=function (grid) {constseen= [];let islandCount =0;for (let i =0; i <grid.length; i++) {seen.push(newArray(grid[0].length).fill(false)); }functionsailingSevenSeas(x, y, prev) {// base conditionif (x <0|| x >=grid.length|| y <0|| y >= grid[0].length) {return; }if (seen[x][y]) {return; }//pre seen[x][y] =true;let currVal = grid[x][y];if (currVal ==="1"&& prev ==="0") {// console.log('found island at:', `${x}, ${y}`) islandCount +=1;// console.log('**** LAND SEARCH PARTY ****')walkTheBeach(x, y); }// console.log('###### ARRRRRRR LETS GO SAILING ######')// recurse and find other 1s until all other 1s turn to 0sailingSevenSeas(x, y +1, currVal);sailingSevenSeas(x +1, y, currVal);sailingSevenSeas(x -1, y, currVal);sailingSevenSeas(x, y +1, currVal);//post }functionwalkTheBeach(x, y) {// base conditionif (x <0|| x >=grid.length|| y <0|| y >= grid[0].length) {return; }if (grid[x][y] ==="0") {// console.log('we are at the beach, mark and return')return; }// claim the contiguos island, other PIRATES can't claim if they can't see it grid[x][y] ="0";// console.log('exploring...')walkTheBeach(x +1, y);walkTheBeach(x, y +1);walkTheBeach(x -1, y);walkTheBeach(x, y -1); }sailingSevenSeas(0,0,"0");return islandCount;};
