मैं डॉ डॉब के लेख का लेखक हूं और कभी-कभी कार्यान्वयन के बारे में पूछता हूं। यहां सी में एक सरल है:
#include
#include
#include
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]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]
यह कंसोल से अपना इनपुट लेता है। आप उदा। इस फ़ाइल को पाइप करें:
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]
उपरोक्त कार्यान्वयन निश्चित रूप से कुछ भी नहीं है, लेकिन यह डॉ। डॉब के लेख में स्पष्टीकरण के बहुत करीब है और जो कुछ भी आवश्यक है उसका अनुवाद करना आसान होना चाहिए।