Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 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 0 Return 4. ? /** 動態規劃的算法?*if(m[i][j] = 1) d[i][j] = min(d[i-1][j-1], d[i][j-1], d[i-1][j]) + 1*m[i][j] = 0; d[i][j] = 0; ? ??*初始化 d[0][j] = m[0][j]; d[i][0] = m[i][0];*優化思路用一行d[j] 進行*int preNode = d[0];*d[0] = m[i][0];* for(int j = 1; j < n; j++)* {?* ? if(m[i][j] = 1) int temp = min(preNode, d[j-1], d[j]) + 1;* ? preNode = d[j];* ? d[j] = temp;* }*錯誤1：沒有考慮<1,0,1,1>向量 ；把矩陣想成等寬高的*/int min(int a, int b){return a < b ? a : b;}int min(int a, int b, int c){return min(min(a,b),min(b,c));} int maximalSquare(vector<vector<char>>& m) {if(m.size() == 0) return 0;int m_size = m.size();// if(m_size == 1) return (m[0][0] == '0') ?

0 : 1; int* d = new int[m[0].size()]; int max = 0; //init for(int i = 0; i < m[0].size(); i++) { d[i] = (m[0][i] == '0') ? 0 : 1; if(d[i] > max) max = d[i]; } //循環 for(int l = 1; l < m_size; l++) //從第1行開始 { int preNode = d[0]; d[0] = (m[l][0] == '0') ?

0 : 1; for(int j = 1; j < m[0].size(); j++) { if(m[l][j] == '0') { preNode = d[j]; d[j] = 0; } else //m[l][j] = 1時 { int temp = min(preNode, d[j-1], d[j]);//d[l-1][j-1], d[l][j-1], d[l-1][j] preNode = d[j]; d[j] = temp + 1; if(d[j] > max) { max = d[j]; } } } } delete d; return max*max; }

版權聲明：本文博主原創文章。博客，未經同意不得轉載。

轉載于:https://www.cnblogs.com/blfshiye/p/4837890.html

總結

以上是生活随笔為你收集整理的Maximal Square 我们都在寻找最高1子矩阵(leeCode)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。