二进制二维数组最大0矩形求解及C代码调试求助

Hey there! I see you're stuck on finding the largest all-0 rectangle in a binary 2D array, and your current code is spitting out garbage values. Let's break this down step by step—first fix the bugs, then implement the histogram method properly for your all-0 use case.

First, Let's Fix the Bugs in Your Current Code #

Your code has a few critical issues that are causing the garbage values and non-functional logic:

1. Missing Header File: You forgot to include <stdio.h>—without this, functions like printf and scanf won't work correctly. Add #include <stdio.h> right after #include "stdafx.h".
2. Incorrect Loop Direction: The loop for (i = row; i < 0; i--) will never run. You want to iterate from the last row up to the first, so it should be for (i = row - 1; i >= 0; i--).
3. Unnecessary Pointer Dereference: *Mat[i][j] is wrong—Mat[i][j] directly gives you the array element value. Just use Mat[i][j] == 0.
4. Unreset temp Variable: You need to reset temp to 0 at the start of each column, otherwise values from previous columns will bleed into the current one.

Here's the corrected code for initializing SumMat (the matrix that tracks consecutive 0s from each row upwards):

#include "stdafx.h"
#include <stdio.h>
#define N 30

int main()
{
    printf("Enter dimensions:\n");
    int i, j, row, col, Mat[N][N], SumMat[N][N];
    int temp, curr;
    scanf("%d %d", &row, &col);
    
    // Read the input matrix
    for (i = 0; i < row; i++) {
        for (j = 0; j < col; j++) {
            scanf("%d", &Mat[i][j]);
        }
    }
    
    // Initialize SumMat: SumMat[i][j] = number of consecutive 0s from row i upwards in column j
    for (j = 0; j < col; j++) {
        temp = 0; // Reset temp for each new column
        for (i = row - 1; i >= 0; i--) { // Iterate from bottom row to top
            if (Mat[i][j] == 0) {
                temp++;
                SumMat[i][j] = temp;
            } else {
                temp = 0;
                SumMat[i][j] = 0; // Make sure to set to 0 when we hit a 1
            }
        }
    }
    
    // Now SumMat is correctly populated—next step: use histogram method on each row
    return 0;
}

Adapting the Histogram Method for All-0 Rectangles #

The histogram method works for all-1 rectangles, and we can adapt it for all-0 by treating SumMat as a set of histograms. Each row in SumMat represents the height of consecutive 0s ending at that row for each column. For each row, we just need to find the largest rectangle in the histogram formed by that row's values—this rectangle corresponds to the largest all-0 rectangle with its base on that row.

To find the largest rectangle in a histogram, we can use a stack-based approach (efficient O(n) time per row). Here's how to implement it:

1. Create a helper function largestRectangleArea that takes an array (histogram) and its length, returns the maximum area.
2. Iterate over each row in SumMat, pass the row to the helper function, and keep track of the maximum area found across all rows.

Full Working Code #

Here's the complete code with the helper function and final logic:

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#define N 30

// Helper function to find largest rectangle in a histogram
int largestRectangleArea(int heights[], int n) {
    int* stack = (int*)malloc(n * sizeof(int));
    int top = -1;
    int maxArea = 0;
    int i = 0;
    
    while (i < n) {
        if (top == -1 || heights[i] >= heights[stack[top]]) {
            stack[++top] = i++;
        } else {
            int height = heights[stack[top--]];
            int width = (top == -1) ? i : i - stack[top] - 1;
            int area = height * width;
            if (area > maxArea) {
                maxArea = area;
            }
        }
    }
    
    while (top != -1) {
        int height = heights[stack[top--]];
        int width = (top == -1) ? i : i - stack[top] - 1;
        int area = height * width;
        if (area > maxArea) {
            maxArea = area;
        }
    }
    
    free(stack);
    return maxArea;
}

int main() {
    printf("Enter dimensions:\n");
    int i, j, row, col, Mat[N][N], SumMat[N][N];
    int temp, maxArea = 0;
    
    scanf("%d %d", &row, &col);
    
    // Read input matrix
    for (i = 0; i < row; i++) {
        for (j = 0; j < col; j++) {
            scanf("%d", &Mat[i][j]);
        }
    }
    
    // Populate SumMat with consecutive 0 heights
    for (j = 0; j < col; j++) {
        temp = 0;
        for (i = row - 1; i >= 0; i--) {
            if (Mat[i][j] == 0) {
                temp++;
                SumMat[i][j] = temp;
            } else {
                temp = 0;
                SumMat[i][j] = 0;
            }
        }
    }
    
    // Calculate max area by checking each row's histogram
    for (i = 0; i < row; i++) {
        int currentArea = largestRectangleArea(SumMat[i], col);
        if (currentArea > maxArea) {
            maxArea = currentArea;
        }
    }
    
    printf("Largest all-0 rectangle area: %d\n", maxArea);
    return 0;
}

Test Example #

Let's say you input:

4 4
1 0 0 0
1 0 1 0
0 0 0 0
0 0 0 1

The SumMat will look like:

0 3 1 2
0 2 0 1
2 1 1 0
1 1 1 0

The largest all-0 rectangle is 6 (3 rows × 2 columns, or 2 rows × 3 columns), and the code will output Largest all-0 rectangle area: 6.

内容的提问来源于stack exchange，提问作者TheCoon