Given a 2D grid of 0s and 1s, return the number of elements in the largest square subgrid that has all 1s on its border, or 0 if such a subgrid doesn’t exist in the grid.
Example 1:
Input: grid = [[1,1,1],[1,0,1],[1,1,1]] Output: 9
Example 2:
Input: grid = [[1,1,0,0]] Output: 1
Constraints:
1 <= grid.length <= 1001 <= grid[0].length <= 100grid[i][j]is0or1
Solution: DP
Compute the sums of all rectangles that has left-top corner at (0, 0) in O(m*n) time.
For each square and check whether its borders are all ones in O(1) time.
Time complexity: O(m*n*min(m,n))
Space complexity: O(m*n)
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 |
// Author: Huahua class Solution { public: int largest1BorderedSquare(vector<vector<int>>& grid) { int n = grid.size(); int m = grid[0].size(); vector<vector<int>> dp(n + 1, vector<int>(m + 1)); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + grid[i - 1][j - 1]; for (int len = min(n, m); len > 0; --len) for (int x1 = 1, x2 = x1 + len - 1; x2 <= m; ++x1, ++x2) for (int y1 = 1, y2 = y1 + len - 1; y2 <= n; ++y1, ++y2) if (getArea(x1, y1, x2, y1, dp) == len && getArea(x1, y1, x1, y2, dp) == len && getArea(x1, y2, x2, y2, dp) == len && getArea(x2, y1, x2, y2, dp) == len) return len * len; return 0; } private: int getArea(int x1, int y1, int x2, int y2, const vector<vector<int>>& dp) { return dp[y2][x2] - dp[y2][x1 - 1] - dp[y1 - 1][x2] + dp[y1 - 1][x1 - 1]; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment