Problem:
Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1‘s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)
Example 1:
|
1 2 3 4 5 6 7 8 |
[[0,0,1,0,0,0,0,1,0,0,0,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,1,1,0,1,0,0,0,0,0,0,0,0], [0,1,0,0,1,1,0,0,1,0,1,0,0], [0,1,0,0,1,1,0,0,1,1,1,0,0], [0,0,0,0,0,0,0,0,0,0,1,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,0,0,0,0,0,0,1,1,0,0,0,0]] |
Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.
Example 2:
|
1 |
[[0,0,0,0,0,0,0,0]] |
Given the above grid, return 0.
Note: The length of each dimension in the given grid does not exceed 50.
Idea:
Use DFS to find the connected components
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 // Runtime: 32 ms class Solution { public: int maxAreaOfIsland(vector<vector<int>>& grid) { int h = grid.size(); if (h == 0) return 0; int w = grid[0].size(); int ans = 0; for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j) ans = max(ans, area(grid, j, i, w, h)); return ans; } private: int area(vector<vector<int>>& grid, int x, int y, int w, int h) { if (x < 0 || y < 0 || x >= w || y >= h || grid[y][x] == 0) return 0; grid[y][x] = 0; return area(grid, x - 1, y, w, h) + area(grid, x + 1, y, w, h) + area(grid, x, y - 1, w, h) + area(grid, x, y + 1, w, h) + 1; } }; |
Related problems:
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
您好,
請問695這題您會錄製影片講解嗎？
謝謝您！
这个题的做法和200题非常类似，可以参考200题的视频：https://www.youtube.com/watch?v=XSmgFKe-XYU
好的，那請問695程式第13行的max要在哪裡定義呢？謝謝！
#include "cmath"