subject
Give you a twodimensional grid composed of '1' (land) and '0' (water). Please calculate the number of islands in the grid.
Islands are always surrounded by water, and each island can only be formed by adjacent land connections in the horizontal and / or vertical direction.
In addition, you can assume that all four sides of the mesh are surrounded by water.
Example 1:
Input: grid =[
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
Example 2:
Input: grid =[
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
Solution 1 dfs
var numIslands = function(grid) { function dfs(grid,i,j){//Format! // Recursive termination condition if(i<0i>=grid.lengthj<0j>=grid[0].lengthgrid[i][j]==='0'){ return } grid[i][j]='0' // The passed is marked with 0 and two brackets ðŸ˜‚ dfs(grid, i + 1, j) dfs(grid, i, j + 1) dfs(grid, i  1, j) dfs(grid, i, j  1) } let count=0 for(let i=0;i<grid.length;i++){ for(let j=0;j<grid[0].length;j++){ if(grid[i][j]==='1'){ dfs(grid,i,j) count++ } } } return count };
Notes:

void traverse(TreeNode root) { // Judge base case if (root == null) { return; } // Access two adjacent nodes: left child node and right child node traverse(root.left); traverse(root.right); } //dfs framework

How to avoid such repeated traversal? The answer is to mark the lattice that has been traversed. Taking the island problem as an example, we need to do DFS traversal on all land grids with a value of 1. Every time we walk through a land grid, we change the value of the grid to 2, so that when we encounter 2, we know that this is the traversed grid. That is, each grid may take three values:
0  Ocean grid
1  land grid (not traversed)
2  land grid (traversed) 
If you do not change the land on the same island with it to 0, DFS will count an island repeatedly when it traverses them

How to find all 1 on the same island
DFS, with current 1 as the entry
What DFS does:
Change the current 1 to 0
The top, bottom, left and right of the current coordinate recurs in turn, and the 1 of the same island becomes 0
dfs exit: out of matrix boundary, or 0 encountered. Don't sink the island, return directly
Solution 2 bfs
const numIslands = (grid) => { let count = 0 let queue = [] for (let i = 0; i < grid.length; i++) { for (let j = 0; j < grid[0].length; j++) { if (grid[i][j] === '1') { count++ grid[i][j] = '0' // Mark to avoid repeated traversal queue.push([i, j]) turnZero(queue, grid) } } } return count } function turnZero(queue, grid) { const dirs = [[0, 1], [1, 0], [0, 1], [1, 0]] while (queue.length) { const cur = queue.shift() for (const dir of dirs) { const x = cur[0] + dir[0] const y = cur[1] + dir[1] if (x < 0  x >= grid.length  y < 0  y >= grid[0].length  grid[x][y] !== '1') { continue } grid[x][y] = '0' queue.push([x, y]) } } }
Notes:
 Count + 1 when encountering 1
Maintain a queue and list its coordinates when it encounters 1
The node is out of the column, and four directions are investigated. If it is 1, it is changed to 0, and the node is listed
If the boundary is exceeded or 0 is encountered, skip and do not enter the column
List out... List in... Until there is no node that can be listed, all 1s of the current island will be turned to 0  A this line is in the first line, and a the children enter the line when they leave the line
Problem solving three parallel search set
class UnionFind { constructor(n) { //Construct a set with n nodes this.count = n //Total number of concurrent search sets this.parent = new Array(n) this.size = new Array(n) // The size array records the weight of each tree for (let i = 0; i < n; i++) { this.parent[i] = i; // You are your own parent this.size[i] = 1; //Number of nodes on each collection } } union(p, q) { //Connected node p and node q, p and q are indexes let rootP = this.find(p); let rootQ = this.find(q); if (rootP === rootQ) return // A small number of elements are connected to a large number of elements, which is more balanced if (this.size[rootP] > this.size[rootQ]) { this.parent[rootQ] = rootP; this.size[rootP] += this.size[rootQ]; } else { this.parent[rootP] = rootQ; this.size[rootQ] += this.size[rootP]; } this.count; } isConnected(p, q) { //Judge whether P and Q are connected return this.find(p) === this.find(q) } find(x) { //Find the root of node x while (this.parent[x] != x) { // Path compression this.parent[x] = this.parent[this.parent[x]]; x = this.parent[x]; } return x; } getCount() { //Returns the number of subsets return this.count; } } var numIslands = function (grid) { let m = grid.length if (m === 0) return 0 let n = grid[0].length const dummy = 1 const dirs = [[1, 0], [0, 1]]//Direction array right down const uf = new UnionFind(m * n) for (let x = 0; x < m; x++) { for (let y = 0; y < n; y++) if (grid[x][y] === '0') {//If the mesh is 0, merge with dummy uf.union(n * x + y, dummy) } else if (grid[x][y] === '1') {//If the grid is 1, try down to the right for (let d of dirs) { let r = x + d[0] let c = y + d[1] if (r >= m  c >= n) continue //Coordinate legitimacy if (grid[r][c] === '1') { //If 1 is below the right side of the current grid, it will be merged with the current grid uf.union(n * x + y, n * r + c) } } } } return uf.getCount() //Return and query the number of sets minus one };
Notes:
 All 0's are fixed and merged, and the last count is reduced by one