1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122  // @Title: 岛屿数量 (Number of Islands) // @Author: 15816537946@163.com // @Date: 2019-11-19 15:04:41 // @Runtime: 0 ms // @Memory: 2.8 MB /* * @lc app=leetcode.cn id=200 lang=golang * * [200] 岛屿数量 * * https://leetcode-cn.com/problems/number-of-islands/description/ * * algorithms * Medium (45.46%) * Likes: 222 * Dislikes: 0 * Total Accepted: 26.5K * Total Submissions: 58.4K * Testcase Example: '[["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]' * * 给定一个由 '1'（陆地）和 * '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。 * * 示例 1: * * 输入: * 11110 * 11010 * 11000 * 00000 * * 输出: 1 * * * 示例 2: * * 输入: * 11000 * 11000 * 00100 * 00011 * * 输出: 3 * * */ /* func numIslands(grid [][]byte) int { n := len(grid) if n == 0 { return 0 } m := len(grid[0]) var dfs func(int, int) dfs = func(i, j int) { grid[i][j] = '0' if 0 <= i-1 && grid[i-1][j] == '1' { dfs(i-1, j) } if 0 <= j-1 && grid[i][j-1] == '1' { dfs(i, j-1) } if i+1 < n && grid[i+1][j] == '1' { dfs(i+1, j) } if j+1 < m && grid[i][j+1] == '1' { dfs(i, j+1) } } var ret int for i := range grid { for j := range grid[0] { if grid[i][j] == '1' { ret++ dfs(i, j) } } } return ret } */ func numIslands(grid [][]byte) int { n := len(grid) if n == 0 { return 0 } m := len(grid[0]) var dfs func(int, int) dfs = func(i, j int) { grid[i][j] = '0' if i > 0 && grid[i-1][j] == '1' { dfs(i-1, j) } if j > 0 && grid[i][j-1] == '1' { dfs(i, j-1) } if i < n-1 && grid[i+1][j] == '1' { dfs(i+1, j) } if j < m-1 && grid[i][j+1] == '1' { dfs(i, j+1) } } var cnt int for i :=range grid { for j := range grid[0] { if grid[i][j] == '1' { cnt++ dfs(i, j) } } } return cnt }