Hello, everyone. Today, I would like to share with you the next LeetCode medium difficulty problem 200. The number of islands

The title

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

Analysis of the

1. Access can only be horizontal or vertical

2.1 is connected to 1, and 0 cannot access it

3. Return the number

solution

1.dfs

2.bfs

Solution a:DFS

Train of thought1.Because it's in two dimensions, we go through each node in two layers2.If encounter'1'We can go, so we do DFS traversal, and we have an island count++3.DFS depth-first traversal1.First of all, if I'm in the matrix isGrid(I,j)2.Set. Has (I +'_'+j) (because duplicate nodes may be accessed)3.The visited nodes are added to the set4.Is a method that accesses the surrounding nodes */var numIslands = function (grid) {
  // Add set to prevent duplicate access
  const set = new Set(a);let res = 0;

  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      // Only values that are '1' and do not exist in set can be accessed in DFS
      if (grid[i][j] === "1" && !set.has(i + "_"+ j)) { visitGridElementDfs(grid, i, j); res++; }}}return res;

  // Check if it is in the matrix
  function inGrid(i, j) {
    return i > -1 && i < grid.length && j > -1 && j < grid[0].length;
  }

  function visitGridElementDfs(grid, i, j) {
    // Does not return in the matrix
    if(! inGrid(i, j)) {return;
    }
    // return on '0'
    if (grid[i][j] === "0") {
      return;
    }
    // Returns on visited nodes
    if (set.has(i + "_" + j)) {
      return;
    }

    set.add(i + "_" + j);

    // Go up
    visitGridElementDfs(grid, i + 1, j);
    // Downward access
    visitGridElementDfs(grid, i - 1, j);
    // Access to the left
    visitGridElementDfs(grid, i, j + 1);
    // Go to the right
    visitGridElementDfs(grid, i, j - 1); }};/* Complexity time O(MN) M is the number of rows, N is the number of columns, space O(MN) */
Copy the code

Method 2:BFS

Train of thought1.Because it's in two dimensions, we go through each node in two layers2.If encounter'1'We can go, so we do DFS traversal, and we have an island count++3.BFS breadth-first traversal1.Start by putting the starting point into a queue2.Take the head of the queue element and judge1.Is it in the matrix2.Have you encountered '0'3.Have you accessed3.If none of the above conditions is met, the elements of each method of this element are queued */var numIslands = function (grid) {
  const seen = new Set(a);let count = 0;
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      // Only values that are '1' and do not exist in set can be accessed in DFS
      if (grid[i][j] === "1" && !seen.has(i + "_"+ j)) { visitGridElementBfs(grid, i, j); count++; }}}return count;

  // Check if it is in the matrix
  function inGrid(i, j) {
    return i > -1 && i < grid.length && j > -1 && j < grid[0].length;
  }

  function visitGridElementBfs(grid, i, j) {
    const list = [];
    list.push([i, j]);

    while (list.length) {
      const cur = list.shift();
      (i = cur[0]), (j = cur[1]);

      if(! inGrid(i, j))continue;
      if (grid[i][j] === "0") continue;
      if (seen.has(i + "_" + j)) continue;

      seen.add(i + "_" + j);
      list.push([i + 1, j]);
      list.push([i - 1, j]);
      list.push([i, j + 1]);
      list.push([i, j - 1]); }}};/* Complexity time O(MN) M is the number of rows and N is the number of columns space O(MN) */
Copy the code

conclusion

How to use DFS to BFS nodes

You can have a look at a column I share (front-end algorithm) where there are more topics about the algorithm to share, I hope to help you, I will try to keep updated every night, if you like the trouble to help me to like, thank you very much

If you’re interested in “TS” check out my column (TypeScript common knowledge) and thank you for supporting it

The purpose of this article is to study, discuss and share the experience in the process of learning algorithm. Some of the materials in this article are from the network. If there is infringement, please contact to delete, [email protected]