2 डी बाइनरी मैट्रिक्स में 1 का सबसे बड़ा आयताकार

Question

0-1 मैट्रिक्स में 1 का अधिकतम क्षेत्र ढूंढने में कोई समस्या है। इस समस्या में दो मामले हैं:

1. मापने के लिए क्षेत्र आकार वर्ग का है। यह डीपी द्वारा सरल है।

2. मापने के लिए क्षेत्र आयताकार के आकार का है। मैं इसके लिए इष्टतम समाधान नहीं सोच पा रहा हूं।

उदाहरण:

010101 
101001 
111101 
110101 

सबसे बड़ा आयत 4 के एक क्षेत्र (3 पंक्ति, 5 वीं स्तंभ और एक 3 में और अधिक, 4 पंक्ति) है। क्या हम उन सभी आयतों को भी प्राप्त कर सकते हैं?

Answer 1

मैं कठिनाई/घटाने वाली रनटाइम जटिलता के कुछ समाधानों के माध्यम से कदम उठाऊंगा।

सबसे पहले, एक ब्रूट फोर्स समाधान। हर संभव आयत उत्पन्न करें। आप आर 1 ≤ आर 2 और सी 1 ≤ सी 2 के साथ प्रत्येक जोड़ी के अंक (आर 1, सी 1) (आर 2, सी 2) के माध्यम से पुनरावृत्ति करके ऐसा कर सकते हैं (लूप के लिए 4 के साथ किया जा सकता है)। यदि एक आयताकार में 0 नहीं है, तो आप क्षेत्र को अब तक के सबसे बड़े क्षेत्र में तुलना करते हैं। यह एक ओ (आर^3 सी^3) है।

हम ओ (1) को वैध आयत जांच को तेज कर सकते हैं। हम ऐसा करते हैं जहां डीपी (आर, सी) आयत में 0 की संख्या ((1, 1), (आर, सी) स्टोर करता है।

• डी पी (आर, 0) = 0
• डी पी (0, ग) = 0
• डी पी (आर, सी) डी पी = (आर -1, ग) + डी पी (r, ग 1) -dp (आर 1, सी 1) + (मैट्रिक्स [आर] [सी] 0: 1)

तो ((आर 1 में 0 की संख्या, सी 1), (r2, c2)) है

• nzeroes (आर 1, सी 1, आर 2, सी 2) = डी पी [r2] [c2] -dp [r1 -1] [c2] -dp [r2] [c1 -1] + डी पी [ आर 1 -1] [सी 1 -1]

फिर आप जांच सकते हैं कि आयताकार nzeroes (r1, c1, r2, c2) == 0 द्वारा मान्य है या नहीं।

एक साधारण डीपी और एक ढेर का उपयोग करके इसके लिए ओ (आर^2 सी) समाधान है। डीपी अगले कॉल तक सेल के ऊपर 1 कोशिकाओं की संख्या को ढूंढकर प्रति कॉलम काम करता है। डीपी निम्नानुसार है:

डीपी (आर, 0) = 0 डीपी (आर, सी) = 0 मैट्रिक्स [आर] [सी] == 0 डी पी (आर, सी) = डी पी (आर -1, ग) + 1 अन्यथा

फिर आप निम्न कार्य करें:

area = 0 
for each row r: 
    stack = {} 
    stack.push((height=0, column=0)) 
    for each column c: 
    height = dp(r, c) 
    c1 = c 
    while stack.top.height > height: 
     c1 = stack.top.column 
     stack.pop() 
    if stack.top.height != height: 
     stack.push((height=height, column=c1)) 
    for item in stack: 
     a = (c - item.column + 1) * item.height 
     area = max(area, a) 

यह करने के लिए भी संभव है ओ (आरसी) में तीन डीपी का उपयोग करके समस्या को हल करें:

• एच (आर, सी): अगर हम (आर, सी) शुरू करते हैं और ऊपर जाते हैं, तो पहले 0 से पहले हमें कितने 1 कोशिकाएं मिलती हैं?
• एल (आर, सी): हम कितने दूर तक आयत (आर, सी) और ऊंचाई एच (आर, सी) पर नीचे-दाएं कोने के साथ एक आयताकार बढ़ा सकते हैं?
• आर (आर, सी): हम (आर, सी) और ऊंचाई एच (आर, सी) पर नीचे-बाएं कोने के साथ एक आयत का विस्तार कैसे कर सकते हैं?

तीन पुनरावृत्ति संबंधों हैं:

• ज (0, ग) = 0
• ज (आर, सी) = 0 यदि मैट्रिक्स [आर] [सी] == 0

• ज (आर, सी) = ज (आर -1, ग) +1 अन्यथा

• एल (आर, 0) = 0

• एल (आर, सी) = सीपी अगर मैट्रिक्स [r- 1] [सी] == 0

• एल (आर, सी) = मिनट (एल (आर - 1, ग), सी - पी) अन्यथा

• आर (आर, सी + 1) = 0

• आर (r, ग) = पीसी अगर मैट्रिक्स [आर 1] [सी] == 0
• आर (r, ग) = मिनट (r (आर - 1, ग), पीसी) अन्यथा

जहां पी पिछले 0 का कॉलम है क्योंकि हम बाएं-दाएं से बाएं और दाएं बाएं से आर को पॉप्युलेट करते हैं।

जवाब तो है:

• max_r, ग (ज (r, ग) * (एल (r, ग) + आर (r, ग) - 1))

यह अवलोकन के कारण काम करता है कि सबसे बड़ा आयताकार हमेशा चारों तरफ 0 (किनारे पर 0 के रूप में कवर होने पर) को स्पर्श करेगा। कम से कम शीर्ष के साथ सभी आयतों पर विचार करके, बाएं और दाएं 0 को स्पर्श करके, हम सभी उम्मीदवार आयतों को कवर करते हैं। हर संभव आयत उत्पन्न करें। आप आर 1 ≤ आर 2 और सी 1 ≤ सी 2 के साथ प्रत्येक जोड़ी के अंक (आर 1, सी 1) (आर 2, सी 2) के माध्यम से पुनरावृत्ति करके ऐसा कर सकते हैं (लूप के लिए 4 के साथ किया जा सकता है)। यदि एक आयताकार में 0 नहीं है, तो आप क्षेत्र को अब तक के सबसे बड़े क्षेत्र में तुलना करते हैं।

नोट: मैंने ऊपर दिए गए उत्तर से here लिखा - "बेन की माँ" अनुभाग का संदर्भ लें। उस लेखन में, 0 पेड़ हैं। उस लेखन में भी बेहतर स्वरूपण है।

Answer 2

मैं निम्नलिखित की कोशिश करेंगे:

(1) जुड़े घटकों में मैट्रिक्स घुलना (BFS के माध्यम से)।

(2) प्रत्येक जुड़े घटक के लिए, अधिकतम आयत की तलाश करें।

करने के लिए (2), मैं पहले लंबवत आयताकारों की तलाश करता हूं: प्रत्येक लगातार (min_y, max_y) के लिए अधिकतम संभव चौड़ाई पाएं, और इसलिए क्षेत्र (इसके अनुसार, ओ (1) प्रति पंक्ति में, केवल देखकर कनेक्टेड घटक की उस पंक्ति में न्यूनतम/अधिकतम 1 में)। फिर मैं मैट्रिक्स को स्थानांतरित कर दूंगा, और प्रक्रिया को दोहरा दूंगा।

बीएफएस के लिए कुल चलने का समय ओ (एमएक्सएन) है, तो कुल ओ (एमएक्सएन + एम^2 + एन^2) के लिए प्रत्येक कनेक्टेड componenet के लिए ओ (चौड़ाई^2 + ऊंचाई^2) है।

मुझे आश्चर्य है कि असीमित रूप से इष्टतम समाधान क्या है।

Answer 3

कई बार हिस्टोग्राम में अधिकतम आयताकार क्षेत्र को खोजने के लिए समस्या को कम किया जा सकता है।

प्रत्येक पंक्ति के बाद, आप उस पंक्ति तक बनाए गए हिस्टोग्राम की गणना करते हैं, और उस हिस्टोग्राम में अधिकतम क्षेत्र आयताकार की गणना करते हैं।

int maximalRectangle(vector<vector<char> > &mat) { 
    int rows=mat.size(); 
    if(rows==0)return 0; 
    int columns = mat[0].size(); 

    int temp[columns]; 
    for(int i=0;i<columns;i++){ 
     temp[i] = mat[0][i]-'0'; 
    } 

    int maxArea=0; 
    maxArea = max(maxArea,maxUtil(temp,columns)); 
    // cout<<"before loop\n"; 
    // print1d(temp,columns); 
    for(int i=1;i<rows;i++){ 
     for(int j=0;j<columns;j++){ 
      temp[j] = (mat[i][j]-'0')?temp[j]+1:0; 
     } 
     // cout<<"after iteration : "<<i<<endl; 
     // print1d(temp,columns); 
     maxArea = max(maxArea,maxUtil(temp,columns)); 
     // cout<<"maxarea = "<<maxArea<<endl; 
    } 
    return maxArea; 
} 

temp प्रत्येक चरण में हिस्टोग्राम है और maxutil उस हिस्टोग्राम में अधिकतम आयताकार क्षेत्र की गणना करता है।

Answer 4

** 

//use this dynamic programming approach 
//The problem can be reduced to finding the maximum rectangle area in a histogram, multiple times. 
After each row, you calculate the histogram built until that row, and that calculate the maximum area rectangle in that histogram. 

**

import java.util.Scanner; 


public class LargestRectInAmatrix { 
    static int row,col,matrix[][]; 
    static int maxArea=0; 
    static int barMatrix[]; 
    public static void main(String[] args) { 
     Scanner sc=new Scanner(System.in); 
     row=sc.nextInt(); 
     col=sc.nextInt(); 
     matrix=new int[row][col]; 
     barMatrix=new int[col]; 
     for(int i=0;i<row;i++) 
     { 
      for(int j=0;j<col;j++) 
      { 
       matrix[i][j]=sc.nextInt(); 
      } 
     } 
     startSolution(); 
     System.out.println(maxArea); 

    } 
    private static void startSolution() 
    { 
     for(int i=0;i<row;i++) 
     { 
      for(int j=0;j<col;j++) 
      { 
      if(matrix[i][j]==0) 
      { 
       barMatrix[j]=0; 
      } 
      else 
       barMatrix[j]=barMatrix[j]+matrix[i][j]; 
      } 
      int area=calculateArea(0,col-1); 
      if(area>maxArea) 
      { 
       maxArea=area; 
      } 
     } 

    } 
    private static int calculateArea(int l,int h) 
    { 
     if(l>h) 
     { 
      return Integer.MIN_VALUE; 
     } 
     if(l==h) 
     { 
      return barMatrix[l]; 
     } 
     int u=calMinimumIndex(l,h); 
     return (max(calculateArea(l, u-1),calculateArea(u+1, h),barMatrix[u]*(h-l+1))); 



    } 
    private static int max(int a,int b,int c) 
    { 
     if(a>b) 
     { 
      if(a>c) 
      { 
       return a; 
      } 
      else 
       return c; 
     } 
     else 
      if(b>c) 
      { 
       return b; 
      } 
      else 
       return c; 
    } 
    private static int calMinimumIndex(int l,int h) 
    { 
     int min=Integer.MAX_VALUE; 
     int min_index=0; 
     for(int i=l;l<=h;i++) 
     { 
      if(barMatrix[i]<min){ 
       min=barMatrix[i]; 
       min_index=i; 
      } 
     } 
     return min_index; 
    } 


} 

Answer 5

एक और सरल तरीका आयतों की लंबाई (पंक्ति और स्तंभ वार) की गणना करने के दो अस्थायी एम एक्स एन सरणियों उपयोग करने के लिए है - तो लगातार 1 के यानी गिनती। अधिकतम दोहराव की लंबाई (पंक्ति और कॉलम वार) खोजने के लिए दो अस्थायी मैट्रिस को पार करें।

यहां कोड भी है।

int GetMaxRectangularArea(vector<vector<int>> & matrix, int nRows, int nCols) 
{ 
    vector<vector<int>> rowLengths(nRows, vector<int>(nCols)); 
    vector<vector<int>> colLengths(nRows, vector<int>(nCols)); 

    // initialize first column of rowLengths with first column of matrix 
    for (int i = 0; i < nRows; i++) { 
     rowLengths[i][0] = matrix[i][0]; 
    } 

    // initialize first row of colLengths with first row of matrix 
    for (int j = 0; j < nCols; j++) { 
     colLengths[0][j] = matrix[0][j]; 
    } 

    // Compute row wise length of consecutive 1's in rowLengths 
    for (int i = 0; i < nRows; i++) { 
     for (int j = 1; j < nCols; j++) { 
      if (matrix[i][j] == 1) { 
       rowLengths[i][j] = 1 + rowLengths[i][j - 1]; 
      } 
      else { 
       rowLengths[i][j] = 0; 
      } 
     } 
    } 

    // Compute column wise length of consecutive 1's in colLengths 
    for (int j = 0; j < nCols; j++) { 
     for (int i = 1; i < nRows; i++) { 
      if (matrix[i][j] == 1) { 
       colLengths[i][j] = 1 + colLengths[i- 1][j]; 
      } 
      else { 
       colLengths[i][j] = 0; 
      } 
     } 
    } 

    // Now traverse the rowLengths array to find max length sub array 
    int maxArea = 0; 

    for (int j = nCols - 1; j >= 0; j--) { 
     int currentArea = 0; 
     int currentMax = -1; 
     int repeats = 1; 

     for (int i = nRows - 1; i >= 0; i--) { 
      if (rowLengths[i][j] != currentMax) { 
       if (currentMax != -1) { 
        currentArea = currentMax * repeats; 

        if (currentArea > maxArea) { 
         maxArea = currentArea; 
        } 
       } 

       currentMax = rowLengths[i][j]; 
       repeats = 1; 
      } 
      else { 
       repeats++; 
      } 
     } 

     currentArea = currentMax * repeats; 

     if (currentArea > maxArea) { 
      maxArea = currentArea; 
     } 
    } 

    for (int i = nRows - 1; i >= 0; i--) { 
     int currentArea = 0; 
     int currentMax = -1; 
     int repeats = 1; 

     for (int j = nCols - 1; j >= 0; j--) { 
      if (colLengths[i][j] != currentMax) { 
       if (currentMax != -1) { 
        currentArea = currentMax * repeats; 

        if (currentArea > maxArea) { 
         maxArea = currentArea; 
        } 
       } 

       currentMax = colLengths[i][j]; 
       repeats = 1; 
      } 
      else { 
       repeats++; 
      } 
     } 

     currentArea = currentMax * repeats; 

     if (currentArea > maxArea) { 
      maxArea = currentArea; 
     } 
    } 

    return maxArea; 
} 

Answer 6

class GfG{ 
    public int maxArea(int a[][],int m,int n){ 
     if(a==null || m==0 || n== 0) return 0; 
     m = a.length; 
     n = a[0].length; 
     int dp[] = new int[n+1]; 
     int height[] = new int[n]; 
     int p = 0; 
     dp[p] = -1; 
     int ans = 0; 
     //System.out.println("1 "); 
     for(int i = 0;i<m;i++){ 
      for(int j = 0;j<n;j++){ 
       if(a[i][j]==1){ 
        height[j] += a[i][j]; 
       } 
       else{ 
        height[j] = 0; 
       } 
      } 
      p= 0; 
      //System.out.println("2 "); 
      for(int j = 0;j<n;j++){ 
       while(p>0 && height[j] < height[dp[p]]){ 
        int start = dp[p-1]; 
        ans = Math.max(ans,(j-start-1)*height[dp[p]]); 
        p--; 
        //System.out.println("1 "); 
       } 
       dp[++p] = j; 
      } 
     } 
     return ans; 
    } 
}