islands

200. Number of islands

Given a two-dimensional grid of ‘1’ (land) and ‘0’ (water), count the number of islands in the grid. Islands are always surrounded by water, and each island can only be formed by connecting adjacent lands horizontally and/or vertically. Furthermore, you can assume that all four sides of the grid are surrounded by water.

Example 1: input: grid = [[" 1 ", "1", "1", "1", "0"], [" 1 ", "1", "0", "1", "0"], [" 1 ", "1", "0" and "0" and "0"], [" 0 ", "0" and "0" and "0" and "0"]] output: 1Copy the code

Depth-first traversal: Loop the two-dimensional array, when encountered 1, set the value to 2, and make recursive judgment of the value before and after, for example, judge whether the right side is 1 until the right side is 0, exit, then to the bottom side, left side, top side, this is depth-first search

function numIslands(grid) { let num = 0; let rows = grid.length; for(let i = 0; i < rows; i++) { let cols = grid[i].length; for(let j = 0; j < cols; j ++) { if(grid[i][j] == 1) { dfs(grid, i, j, rows, cols); Num ++}}}} // Rows and cols are used to determine whether the boundary is crossed, Function DFS (grid, I, j, rows, function DFS (grid, I, j, rows, Cols) {/ / recursive termination conditions the if (I < 0 | | I > rows | | j < 0 | | j > cols | | grid [I] [j]. = 1) return grid[i][j] = 2 dfs(grid, i + 1, j, rows, cols) dfs(grid, i - 1, j, rows, cols) dfs(grid, i, j + 1, rows, cols) dfs(grid, i, j - 1, rows, cols) }Copy the code

When the value is 1, put the corresponding [I, j] into the queue and set the value to 2. Then loop through the queue and take out a [I, j] from the queue to determine whether the value is 1. If it is 1, put it into the end of the queue. Until the queue is empty, the current island is found and the search continues for the next island

function numIslands(grid) { let queue = []; // let num = 0; // let rows = grid.length - 1; For (let I = 0; i < grid.length; i++) { let cols = grid[i].length - 1; For (let j = 0; j < grid[i].length; j++) { if (grid[i][j] == 1) { queue.push([i, j]); Grid [I][j] = 2; While (queue. Length > 0) {let [x, y] = queue. Shift (); if (x - 1 >= 0 && grid[x - 1][y] == 1) { queue.push([x - 1, y]); grid[x - 1][y] = 2; } if (x + 1 <= rows && grid[x + 1][y] == 1) {queue. Push ([x + 1, y]); grid[x + 1][y] = 2; } if (y + 1 <= cols && grid[x][y + 1] == 1) { queue.push([x, y + 1]); grid[x][y + 1] = 2; } if (y - 1 >= 0 && grid[x][y - 1] == 1) { queue.push([x, y - 1]); grid[x][y - 1] = 2; } } num++; } } } return num; }Copy the code

The breadth-first algorithm is not an in-place algorithm and requires a queue for storage, so memory consumption is high and depth-first is not needed

Time complexity: O(MN), each value needs to be traversed once Space complexity: O(MN), there are MN function context stored in the stack