Problem:
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
|
1 2 3 4 |
11110 11010 11000 00000 |
Answer: 1
Example 2:
|
1 2 3 4 |
11000 11000 00100 00011 |
Idea: DFS
Use DFS to find a connected component (an island) and mark all the nodes to 0.
Time complexity: O(mn)
Space complexity: O(mn)
Solution
C++
|
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 |
// Author: Huahua // Time complexity: O(mn) // Running time: 6 ms class Solution { public: int numIslands(vector<vector<char>>& grid) { if (grid.empty()) return 0; int m = grid.size(); int n = grid[0].size(); int ans = 0; for (int y = 0; y < m; ++y) for (int x = 0; x < n; ++x) { ans += grid[y][x] - '0'; dfs(grid, x, y, m, n); } return ans; } private: void dfs(vector<vector<char>>& grid, int x, int y, int m, int n) { if (x < 0 || y < 0 || x >= n || y >= m || grid[y][x] == '0') return; grid[y][x] = '0'; dfs(grid, x + 1, y, m, n); dfs(grid, x - 1, y, m, n); dfs(grid, x, y + 1, m, n); dfs(grid, x, y - 1, m, n); } }; |
Java
|
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 |
// Author: Huahua // Time Complexity: O(mn) // Running time: 13 ms class Solution { public int numIslands(char[][] grid) { int m = grid.length; if (m == 0) return 0; int n = grid[0].length; int ans = 0; for (int y = 0; y < m; ++y) for (int x = 0; x < n; ++x) if (grid[y][x] == '1') { ++ans; dfs(grid, x, y, n, m); } return ans; } private void dfs(char[][] grid, int x, int y, int n, int m) { if (x < 0 || y < 0 || x >= n || y >= m || grid[y][x] == '0') return; grid[y][x] = '0'; dfs(grid, x + 1, y, n, m); dfs(grid, x - 1, y, n, m); dfs(grid, x, y + 1, n, m); dfs(grid, x, y - 1, n, m); } } |
Python
|
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 |
""" Author: Huahua Time Complexity: O(mn) Running Time: 102 ms """ class Solution(object): def numIslands(self, grid): """ :type grid: List[List[str]] :rtype: int """ m = len(grid) if m == 0: return 0 n = len(grid[0]) ans = 0 for y in xrange(m): for x in xrange(n): if grid[y][x] == '1': ans += 1 self.__dfs(grid, x, y, n, m) return ans def __dfs(self, grid, x, y, n, m): if x < 0 or y < 0 or x >=n or y >= m or grid[y][x] == '0': return grid[y][x] = '0' self.__dfs(grid, x + 1, y, n, m) self.__dfs(grid, x - 1, y, n, m) self.__dfs(grid, x, y + 1, n, m) self.__dfs(grid, x, y - 1, n, m) |
Related Problems
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment