Advertisement
Guest User

Untitled

a guest
Jun 14th, 2023
839
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. var numIslands = function (grid) {
  2.  
  3.     let numberOfIslands = 0;
  4.     let currentMode = "find_land";
  5.     let numberOfSubArrays = grid.length;
  6.     let eachSubArraySize = grid[0]?.length;
  7.     let bfsQueue = [];
  8.     let blocksAddedToTheFrontier = {}
  9.     let continueMainLoop = true;
  10.  
  11.     let currentExplorationIndex = {
  12.         subArrayIndex: 0,
  13.         subArrayElementIndex: 0
  14.     }
  15.  
  16.     if (numberOfSubArrays == 0 || eachSubArraySize == 0) {
  17.         return 0;
  18.     }
  19.  
  20.     const moveToNextLocation = () => {
  21.         let newSubArrayIndex = currentExplorationIndex.subArrayIndex;
  22.         let newSubArrayElementIndex = currentExplorationIndex.subArrayElementIndex + 1;
  23.  
  24.         if (newSubArrayElementIndex == eachSubArraySize) {
  25.             newSubArrayElementIndex = 0;
  26.             newSubArrayIndex = newSubArrayIndex + 1;
  27.         }
  28.  
  29.         if (newSubArrayIndex == numberOfSubArrays) {
  30.             currentExplorationIndex = {
  31.                 subArrayIndex: undefined,
  32.                 subArrayElementIndex: undefined
  33.             }
  34.             continueMainLoop = false;
  35.             return;
  36.         }
  37.  
  38.         currentExplorationIndex = {
  39.             subArrayIndex: newSubArrayIndex,
  40.             subArrayElementIndex: newSubArrayElementIndex
  41.         }
  42.     }
  43.  
  44.     const addLocationToQueue = (locationObj) => {
  45.         let hashKey = `${locationObj.subArrayIndex}-${locationObj.subArrayElementIndex}`;
  46.         if (blocksAddedToTheFrontier[hashKey] == true) {
  47.             return;
  48.         } else {
  49.             blocksAddedToTheFrontier[hashKey] = true;
  50.             bfsQueue.push({ ...locationObj })
  51.         }
  52.     }
  53.  
  54.     const expandFrontier = (startingBlock) => {
  55.         let blockAbove = {
  56.             subArrayIndex: startingBlock.subArrayIndex - 1,
  57.             subArrayElementIndex: startingBlock.subArrayElementIndex
  58.         }
  59.  
  60.         let blockBelow = {
  61.             subArrayIndex: startingBlock.subArrayIndex + 1,
  62.             subArrayElementIndex: startingBlock.subArrayElementIndex
  63.         }
  64.  
  65.         let blockOnRight = {
  66.             subArrayIndex: startingBlock.subArrayIndex,
  67.             subArrayElementIndex: startingBlock.subArrayElementIndex + 1
  68.         }
  69.  
  70.         let blockOnLeft = {
  71.             subArrayIndex: startingBlock.subArrayIndex,
  72.             subArrayElementIndex: startingBlock.subArrayElementIndex - 1
  73.         }
  74.  
  75.         let allPossibleBlockToAddToFrontier = [
  76.             blockAbove, blockBelow, blockOnRight, blockOnLeft
  77.         ]
  78.  
  79.         let onlyBlocksThatHaveLand = allPossibleBlockToAddToFrontier.filter((block) => {
  80.             let valueAtThisLocation = undefined;
  81.             try {
  82.                 valueAtThisLocation = grid[block.subArrayIndex][block.subArrayElementIndex];
  83.             } catch { }
  84.             return (valueAtThisLocation == '1');
  85.         })
  86.  
  87.         onlyBlocksThatHaveLand.forEach((block) => {
  88.             addLocationToQueue(block);
  89.         })
  90.     }
  91.  
  92.     const conquerLand = () => {
  93.         let locationFromQueue = bfsQueue.shift();
  94.  
  95.         if (locationFromQueue != undefined) {
  96.             expandFrontier(locationFromQueue);
  97.         } else {
  98.             numberOfIslands += 1;
  99.             currentMode = 'find_land';
  100.         }
  101.     }
  102.  
  103.     const isThereLandAtThisLocation = () => {
  104.         return grid[currentExplorationIndex.subArrayIndex][currentExplorationIndex.subArrayElementIndex] == '1';
  105.     }
  106.  
  107.     const executeFindLand = () => {
  108.         if (isThereLandAtThisLocation()) {
  109.  
  110.             // We have found land, so we start to conquer it
  111.             addLocationToQueue(currentExplorationIndex);
  112.  
  113.             if (bfsQueue.length > 0) {
  114.                 currentMode = 'conquer_land';
  115.             } else {
  116.                 // This is not new land
  117.                 moveToNextLocation()
  118.             }
  119.         } else {
  120.             // We have not found land, so we..
  121.             moveToNextLocation()
  122.         }
  123.     }
  124.  
  125.     while (continueMainLoop) {
  126.  
  127.         if (currentMode == 'find_land') {
  128.             executeFindLand();
  129.         } else {
  130.             conquerLand();
  131.         }
  132.  
  133.     }
  134.  
  135.     return numberOfIslands;
  136. }
  137.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement