This is the 14th day of my participation in the August Text Challenge.More challenges in August

Difficulty: Medium

Topic describes

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: the grid = [[" 1 ", "1", "1", "1", "0"], [" 1 ", "1", "0", "1", "0"], [" 1 ", "1", "0" and "0" and "0"], [" 0 "and" 0 ", "0" and "0", "0"]]Copy the code

Output: 1.

Example 2:

Input: the grid = [[" 1 ", "1", "0" and "0" and "0"], [" 1 ", "1", "0" and "0" and "0"], [" 0 "and" 0 ", "1", "0" and "0"], [" 0 "and" 0 ", "0", "1", "1"]]Copy the code

Output: 3

Tip:

M == grid. Length n == grid[I]. Length 1 <= m, n <= 300 grid[I]Copy the code

Their thinking

Deep search + wide search + and search the collection

  • Depth-first search: Find the number of connected blocks

    • Each deep search can traverse one connected block in the graph, so the number of deep searches is the number of connected blocks
    • Every time a “1” is accessed, it is replaced with a “0” instead of the visD array indicating whether the node has been accessed

  • Depth-first search

Class Solution: def self, grid: List[List[STR]]) -> int: self, grid: List[STR]] grid[i][j] = '0' for x, y in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]: if x>=0 and x<n and y>=0 and y<m and grid[x][y]=='1': dfs(x, y) n, m = len(grid), len(grid[0]) res = 0 for i in range(n): for j in range(m): If grid[I][j] == '1': res += 1 DFS (I, j) return resCopy the code
  • Breadth-first search
  • Using breadth-first search, the number of searches is the number of connected blocks, i.e. the number of islands
Class Solution: def self, grid: List[List[STR]]) -> int: self, grid: List[STR]] queue = [(i, j)] grid[i][j] = "0" while queue: x, y = queue.pop(0) for a, b in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]: if a>=0 and a<n and b>=0 and b<m and grid[a][b]=="1": queue.append((a, b)) grid[a][b] = "0" n, m = len(grid), len(grid[0]) res = 0 for i in range(n): for j in range(m): if grid[i][j] == "1": res += 1 bfs(i, j) return resCopy the code
  • Check and set
    • Initialize each location as a collection, uniquely identifying each element with I *col+j
    • Initializes the size = col. * the row
    • The connected elements are merged into a set, and each merge is size-1
    • Final size = number of connected blocks + number of water elements
    • So when you iterate over each element, count the number of water
    • Number of islands = size – number of water
Class Solution: def numIslands(self, grid: List[List[STR]]) -> int: Self. P = [I for I in range(n)] def find(self, x): If self.p[x]! = x: self.p[x] = self.find(self.p[x]) return self.p[x] def union(self, a, b): Ar, br = self.find(a), self.find(b) # if ar == br: return # not in the same set, merge else: Self. p[ar] = br self.size -= 1 n, m = len(grid), len(grid[0]) ocean = 0 uf = unionFind(n*m) for I in range(n): If grid[I][j]==" 0": ocean += 1 else: if grid[I][j]=="1": ocean += 1 uf.union(i*m+j, (i+1)*m+j) if j+1 < m and grid[i][j+1]=="1": uf.union(i*m+j, i*m+(j+1)) return uf.size - oceanCopy the code