/* * @lc app=leetcode id=200 lang=javascript * * [200] Number of Islands */ // @lc code=start /** * @param {character[][]} grid * @return {number} */ var numIslands = function (grid) { var run = true; var islands = 0; while (run != false) { const res = getStart(grid); if (res == false) { run = false; break; } queue.slots[queue.last] = res; queue.last++; while (queue.last > 0) { searchLand(grid); } islands++; } return islands; }; const directions = { UP: { x: 0, y: 1 }, LEFT: { x: -1, y: 0 }, DOWN: { x: 0, y: -1 }, RIGHT: { x: 1, y: 0 }, }; const isOutOfBounds = (grid, tile) => { const gridMinX = 0; const gridMinY = 0; const gridMaxX = grid.length - 1; const gridMaxY = grid[0].length - 1; return ( tile.x < gridMinX || tile.x > gridMaxX || tile.y < gridMinY || tile.y > gridMaxY ); }; const getStart = (grid) => { for (let i = 0; i < grid.length; i++) { for (let j = 0; j < grid[i].length; j++) { if (grid[i][j] == 1) { return tile(i, j); } } } return false; }; const queue = { slots: [], last: 0, }; const tile = (x, y) => { return { x, y }; }; const addTile = (x, y, dir, grid) => { const currentTile = tile(x + dir.x, y + dir.y); if (!isOutOfBounds(grid, currentTile)) { const val = grid[currentTile.x][currentTile.y]; if (val == 1) { queue.slots[queue.last] = currentTile; queue.last++; } } }; const searchLand = (grid) => { let x = queue.slots[queue.last - 1].x; let y = queue.slots[queue.last - 1].y; queue.last--; grid[x][y] = 0; addTile(x, y, directions.UP, grid); addTile(x, y, directions.DOWN, grid); addTile(x, y, directions.LEFT, grid); addTile(x, y, directions.RIGHT, grid); }; // @lc code=end