Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
For example, given the following matrix:
1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0Return 4.
[Thoughts]
这是个DP问题,定义
DP[i, j] 是the length of max square,这个square的最右下角是 (i,j),那么
如果matrix[i][j] == 0, DP[i, j]也是0,因为square 不存在
如果matrix[i][j] == 1, 那么DP[i, j]就有如下三种可能
1)从DP[i-1, j]表述的square上加一行
2)从DP[i, j-1]表述的square上加一列
3)从DP[i-1, j-1]表述的square上加一行和一列
从三种可能中选出最小的那一个就是maximal square。
[Code]
1: int maximalSquare(vector<vector<char>>& matrix) {
2: if(matrix.size() == 0) return 0;
3:
4: int row = matrix.size();
5: int col = matrix[0].size();
6: vector<vector<int>> dp(row+1, vector<int>(col+1, 0));
7:
8: int maxLen = 0;
9: for(int i =1; i<=row; i++) {
10: for(int j =1; j<= col; j++) {
11: if(matrix[i-1][j-1] == '1') {
12: dp[i][j] = min(min(dp[i-1][j-1], dp[i-1][j]), dp[i][j-1])+1 ;
13: maxLen = max(maxLen, dp[i][j]);
14: }
15: }
16: }
17: return maxLen*maxLen;
18: }
1 comment:
Feel divinely connected while staying well-groomed with Apna Showroom’s pooja and grooming combo. It includes pure Gangajal Kalash Lota from Har Ki Pauri, a Shaligram Shivling, a rose brooch, a lice comb, and a premium hair comb made for women and girls. APNA SHOWROOM Bra for Women Combo Pack of 6 - Cup Size 36(B) Non-Wired Multicolor Everyday Cotton Bra 36B
APNA SHOWROOM Bra for Women Combo Pack of 6 - Cup Size 32(B) Non-Wired Multicolor Everyday Cotton Bra 32B
APNA SHOWROOM Bra for Women Combo Pack of 6 - Cup Size 34(B) Non-Wired Multicolor Everyday Cotton Bra 34B
Apna Showroom Ganga Jal - Holy pure Ganga Jal Har ki pauri Brahmakund Prasad Tasveer Chunni Haridwar Ganga Jal Natural Ganga jal
APNA SHOWROOM Rudraksha Mala 5 Panchmukhi Authentic Genuine Rudraksha Beads Ornament Rosary Japa Mala Beads Necklace Puja | Prayer (108+1) Beads | 10mm Mala
The comb’s design ensures easy styling and comfort. Whether used for rituals, daily grooming, or sacred gifting, this combo supports both spiritual growth and personal elegance. A thoughtful balance of tradition and utility.
Post a Comment