पहेली: सबसे बड़ा आयताकार (अधिकतम आयत समस्या)

Question

खाली स्थान में फिट होने वाले सबसे बड़े क्षेत्र के साथ आयत को खोजने के लिए सबसे कुशल एल्गोरिदम क्या है?

चलो कहते हैं कि स्क्रीन की तरह इस ('#' भरा दर्शाता क्षेत्र) लग रहा है:

.................... 
..............###### 
##.................. 
.................### 
.................### 
#####............... 
#####............... 
#####............... 

एक संभावित समाधान है:

.................... 
..............###### 
##...++++++++++++... 
.....++++++++++++### 
.....++++++++++++### 
#####++++++++++++... 
#####++++++++++++... 
#####++++++++++++... 

आम तौर पर मैं एक समाधान पता लगाना का आनंद चाहते हैं। यद्यपि इस बार मैं अपने आप को चारों ओर झुकाव बर्बाद करने से बचाना चाहता हूं क्योंकि इस परियोजना के लिए व्यावहारिक उपयोग है जिस पर मैं काम कर रहा हूं। क्या कोई ज्ञात समाधान है?

Shog9 लिखा है:

एक सरणी (के रूप में अन्य प्रतिक्रियाओं से गर्भित), या (मनमाने ढंग से आकार, तैनात आयतों के रूप में अवरोध की एक सूची के रूप में में मामला हो सकता है आपके इनपुट है खिड़की की स्थिति से निपटने के दौरान एक खिड़की प्रणाली)?

हाँ, मेरे पास एक संरचना है जो स्क्रीन पर रखी गई खिड़कियों के एक सेट का ट्रैक रखती है। मेरे पास एक ग्रिड भी है जो प्रत्येक किनारे के बीच के सभी क्षेत्रों का ट्रैक रखता है, चाहे वे खाली हों या भरे हों, और उनके बाएं या शीर्ष किनारे की पिक्सेल स्थिति हो। मुझे लगता है कि कुछ संशोधित रूप हैं जो इस संपत्ति का लाभ उठाएंगे। किसी के बारे में पता है?

Answer 1

@lassevk

मैं संदर्भित लेख, DDJ से मिला: The Maximal Rectangle Problem

Answer 2

यहां एक ऐसा पृष्ठ है जिसमें कुछ कोड और कुछ विश्लेषण हैं।

आपकी विशेष समस्या पृष्ठ पर थोड़ी सी शुरू होती है, पाठ अधिकतम आयत समस्या के लिए पृष्ठ खोजें।

http://www.seas.gwu.edu/~simhaweb/cs151/lectures/module6/module6.html

Answer 3

@lassevk

// 4. Outer double-for-loop to consider all possible positions 
    // for topleft corner. 
    for (int i=0; i < M; i++) { 
     for (int j=0; j < N; j++) { 

     // 2.1 With (i,j) as topleft, consider all possible bottom-right corners. 

     for (int a=i; a < M; a++) { 
      for (int b=j; b < N; b++) { 

haha ​​... हे (एम 2 n2) .. यही कारण है कि शायद मैं क्या लेकर आए हैं जाएगा।

मुझे लगता है कि वे ऑप्टमाइज़ेशन विकसित करने के लिए आगे बढ़ते हैं ... अच्छा लगता है, मुझे पढ़ा जाएगा।

Answer 4

मुझे लगता है कि डॉ डॉब के लेख के लेखक हूँ और कभी कभी एक कार्यान्वयन के बारे में पूछा मिलता है। यहां सी:

#include <assert.h> 
#include <stdio.h> 
#include <stdlib.h> 

typedef struct { 
    int one; 
    int two; 
} Pair; 

Pair best_ll = { 0, 0 }; 
Pair best_ur = { -1, -1 }; 
int best_area = 0; 

int *c; /* Cache */ 
Pair *s; /* Stack */ 
int top = 0; /* Top of stack */ 

void push(int a, int b) { 
    s[top].one = a; 
    s[top].two = b; 
    ++top; 
} 

void pop(int *a, int *b) { 
    --top; 
    *a = s[top].one; 
    *b = s[top].two; 
} 


int M, N; /* Dimension of input; M is length of a row. */ 

void update_cache() { 
    int m; 
    char b; 
    for (m = 0; m!=M; ++m) { 
    scanf(" %c", &b); 
    fprintf(stderr, " %c", b); 
    if (b=='0') { 
     c[m] = 0; 
    } else { ++c[m]; } 
    } 
    fprintf(stderr, "\n"); 
} 


int main() { 
    int m, n; 
    scanf("%d %d", &M, &N); 
    fprintf(stderr, "Reading %dx%d array (1 row == %d elements)\n", M, N, M); 
    c = (int*)malloc((M+1)*sizeof(int)); 
    s = (Pair*)malloc((M+1)*sizeof(Pair)); 
    for (m = 0; m!=M+1; ++m) { c[m] = s[m].one = s[m].two = 0; } 
    /* Main algorithm: */ 
    for (n = 0; n!=N; ++n) { 
    int open_width = 0; 
    update_cache(); 
    for (m = 0; m!=M+1; ++m) { 
     if (c[m]>open_width) { /* Open new rectangle? */ 
     push(m, open_width); 
     open_width = c[m]; 
     } else /* "else" optional here */ 
     if (c[m]<open_width) { /* Close rectangle(s)? */ 
     int m0, w0, area; 
     do { 
      pop(&m0, &w0); 
      area = open_width*(m-m0); 
      if (area>best_area) { 
      best_area = area; 
      best_ll.one = m0; best_ll.two = n; 
      best_ur.one = m-1; best_ur.two = n-open_width+1; 
      } 
      open_width = w0; 
     } while (c[m]<open_width); 
     open_width = c[m]; 
     if (open_width!=0) { 
      push(m0, w0); 
     } 
     } 
    } 
    } 
    fprintf(stderr, "The maximal rectangle has area %d.\n", best_area); 
    fprintf(stderr, "Location: [col=%d, row=%d] to [col=%d, row=%d]\n", 
        best_ll.one+1, best_ll.two+1, best_ur.one+1, best_ur.two+1); 
    return 0; 
} 

यह कंसोल से अपना इनपुट लेता है। आप उदा। यह करने के लिए इस फ़ाइल को पाइप:

16 12 
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 
0 0 0 1 1 0 0 1 0 0 0 1 1 0 1 0 
0 0 0 1 1 0 1 1 1 0 1 1 1 0 1 0 
0 0 0 0 1 1 * * * * * * 0 0 1 0 
0 0 0 0 0 0 * * * * * * 0 0 1 0 
0 0 0 0 0 0 1 1 0 1 1 1 1 1 1 0 
0 0 1 0 0 0 0 1 0 0 1 1 1 0 1 0 
0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 

और बाद अपने इनपुट मुद्रण, यह उत्पादन:

The maximal rectangle has area 12. 
Location: [col=7, row=6] to [col=12, row=5] 

कार्यान्वयन ऊपर निश्चित रूप से कुछ भी नहीं फैंसी है, लेकिन यह बहुत डॉ में स्पष्टीकरण के काफी करीब है डॉब के लेख और जो कुछ भी आवश्यक है अनुवाद करने के लिए आसान होना चाहिए।

Answer 5

मैंने जावा में डॉब्स के समाधान को लागू किया।

किसी भी चीज़ के लिए कोई वारंटी नहीं।

package com.test; 

import java.util.Stack; 

public class Test { 

    public static void main(String[] args) { 
     boolean[][] test2 = new boolean[][] { new boolean[] { false, true, true, false }, 
       new boolean[] { false, true, true, false }, new boolean[] { false, true, true, false }, 
       new boolean[] { false, true, false, false } }; 
     solution(test2); 
    } 

    private static class Point { 
     public Point(int x, int y) { 
      this.x = x; 
      this.y = y; 
     } 

     public int x; 
     public int y; 
    } 

    public static int[] updateCache(int[] cache, boolean[] matrixRow, int MaxX) { 
     for (int m = 0; m < MaxX; m++) { 
      if (!matrixRow[m]) { 
       cache[m] = 0; 
      } else { 
       cache[m]++; 
      } 
     } 
     return cache; 
    } 

    public static void solution(boolean[][] matrix) { 
     Point best_ll = new Point(0, 0); 
     Point best_ur = new Point(-1, -1); 
     int best_area = 0; 

     final int MaxX = matrix[0].length; 
     final int MaxY = matrix.length; 

     Stack<Point> stack = new Stack<Point>(); 
     int[] cache = new int[MaxX + 1]; 

     for (int m = 0; m != MaxX + 1; m++) { 
      cache[m] = 0; 
     } 

     for (int n = 0; n != MaxY; n++) { 
      int openWidth = 0; 
      cache = updateCache(cache, matrix[n], MaxX); 
      for (int m = 0; m != MaxX + 1; m++) { 
       if (cache[m] > openWidth) { 
        stack.push(new Point(m, openWidth)); 
        openWidth = cache[m]; 
       } else if (cache[m] < openWidth) { 
        int area; 
        Point p; 
        do { 
         p = stack.pop(); 
         area = openWidth * (m - p.x); 
         if (area > best_area) { 
          best_area = area; 
          best_ll.x = p.x; 
          best_ll.y = n; 
          best_ur.x = m - 1; 
          best_ur.y = n - openWidth + 1; 
         } 
         openWidth = p.y; 
        } while (cache[m] < openWidth); 
        openWidth = cache[m]; 
        if (openWidth != 0) { 
         stack.push(p); 
        } 
       } 
      } 
     } 

     System.out.printf("The maximal rectangle has area %d.\n", best_area); 
     System.out.printf("Location: [col=%d, row=%d] to [col=%d, row=%d]\n", best_ll.x + 1, best_ll.y + 1, 
       best_ur.x + 1, best_ur.y + 1); 
    } 

} 

Answer 6

इतना संघर्ष कर मैं इस एल्गोरिथ्म लिखा है ... बस कोड को देखने के बाद ...

आप है.यह कोड बोलती समझते हैं !!

import java.util.Scanner; 
import java.util.Stack; 

/** 
* Created by BK on 05-08-2017. 
*/ 
public class LargestRectangleUnderHistogram { 
    public static void main(String... args) { 
     Scanner scanner = new Scanner(System.in); 
     int n = scanner.nextInt(); 
     int[] input = new int[n]; 
     for (int j = 0; j < n; j++) { 
      input[j] = scanner.nextInt(); 
     } 



     /* 
     * This is the procedure used for solving : 
     * 
     * Travel from first element to last element of the array 
     * 
     * If stack is empty add current element to stack 
     * 
     * If stack is not empty check for the top element of stack if 
     * it is smaller than the current element push into stack 
     * 
     * If it is larger than the current element pop the stack until we get an 
     * element smaller than the current element or until stack becomes empty 
     * 
     * After popping each element check if the stack is empty or not.. 
     * 
     * If stack is empty it means that this is the smallest element encountered till now 
     * 
     * So we can multiply i with this element to get a big rectangle which is contributed by 
     * 
     * this 
     * 
     * If stack is not empty then check for individual areas(Not just one bar individual area means largest rectangle by this) (i-top)*input[top] 
     * 
     * 
     * */ 

     /* 
     * Initializing the maxarea as we check each area with maxarea 
     */ 

     int maxarea = -1; 
     int i = 0; 
     Stack<Integer> stack = new Stack<>(); 
     for (i = 0; i < input.length; i++) { 

      /* 
      * Pushing the element if stack is empty 
      * */ 


      if (stack.isEmpty()) { 
       stack.push(i); 
      } else { 

       /* 
       * If stack top element is less than current element push 
       * */ 

       if (input[stack.peek()] < input[i]) { 
        stack.push(i); 
       } else { 

        /* 
        * Else pop until we encounter an element smaller than this in stack or stack becomes empty 
        * 
        * */ 


        while (!stack.isEmpty() && input[stack.peek()] > input[i]) { 

         int top = stack.pop(); 

         /* 
         * If stack is empty means this is the smallest element encountered so far 
         * 
         * So we can multiply this with i 
         * */ 

         if (stack.isEmpty()) { 
          maxarea = maxarea < (input[top] * i) ? (input[top] * i) : maxarea; 
         } 

         /* 
         * If stack is not empty we find areas of each individual rectangle 
         * Remember we are in while loop 
         */ 

         else { 
          maxarea = maxarea < (input[top] * (i - top)) ? (input[top] * (i - top)) : maxarea; 
         } 
        } 
        /* 
        * Finally pushing the current element to stack 
        * */ 

        stack.push(i); 
       } 
      } 
     } 

     /* 
     * This is for checking if stack is not empty after looping the last element of input 
     * 
     * This happens if input is like this 4 5 6 1 2 3 4 5 
     * 
     * Here 2 3 4 5 remains in stack as they are always increasing and we never got 
     * 
     * a chance to pop them from stack by above process 
     * 
     * */ 


     while (!stack.isEmpty()) { 

      int top = stack.pop(); 

      maxarea = maxarea < (i - top) * input[top] ? (i - top) * input[top] : maxarea; 
     } 

     System.out.println(maxarea); 
    } 
}