Problem
In a 2D grid of 0s and 1s, we change at most one 0 to a 1.
After, what is the size of the largest island? (An island is a 4-directionally connected group of 1s).
Example 1:
Input: [[1, 0], [0, 1]] Output: 3 Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.
Example 2:
Input: [[1, 1], [1, 0]] Output: 4 Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 1.
Example 3:
Input: [[1, 1], [1, 1]] Output: 4 Explanation: Can't change any 0 to 1, only one island with area = 1.
Notes:
1 <= grid.length = grid[0].length <= 50.0 <= grid[i][j] <= 1.
Solution
Step 1: give each connected component a unique id and count its ara.
Step 2: for each 0 zero, check its 4 neighbours, sum areas up by unique ids.
Time complexity: O(n*m)
Space complexity: O(n*m)
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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
// Author: Huahua // Running time: 14 ms class Solution { public: int largestIsland(vector<vector<int>>& grid) { color_ = 1; g_ = &grid; m_ = grid.size(); n_ = grid[0].size(); unordered_map<int, int> areas; // color -> area int ans = 0; for (int i = 0; i < m_; ++i) for (int j = 0; j < n_; ++j) if (grid[i][j] == 1) { ++color_; areas[color_] = getArea(j, i); ans = max(ans, areas[color_]); } for (int i = 0; i < m_; ++i) for (int j = 0; j < n_; ++j) if (grid[i][j] == 0) { int area = 1; for (int color : set<int>{getColor(j, i - 1), getColor(j, i + 1), getColor(j - 1, i), getColor(j + 1, i)}) area += areas[color]; ans = max(ans, area); } return ans; } private: int m_; int n_; int color_; vector<vector<int>>* g_; // does not own the object. int getColor(int x, int y) { return (x < 0 || x >= n_ || y < 0 || y >= m_) ? 0 : (*g_)[y][x]; } // Return the area of a connected component, set all elements to color_. int getArea(int x, int y) { if (x < 0 || x >= n_ || y < 0 || y >= m_ || (*g_)[y][x] != 1) return 0; (*g_)[y][x] = color_; return 1 + getArea(x - 1, y) + getArea(x + 1, y) + getArea(x, y - 1) + getArea(x, y + 1); } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment