我不知道哪里错了,45分,B4005
查看原帖
我不知道哪里错了,45分,B4005
1401036
diwurengexianzhi楼主2024/12/1 15:45
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <climits>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> grid(n, vector<int>(m));
    vector<vector<int>> prefixBlack(n + 1, vector<int>(m + 1, 0));
    vector<vector<int>> prefixWhite(n + 1, vector<int>(m + 1, 0));
    
    // 读取网格图
    for (int i = 0; i < n; ++i) {
        string row;
        cin >> row;
        for (int j = 0; j < m; ++j) {
            grid[i][j] = row[j] - '0';
        }
    }
    
    // 计算前缀和
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            prefixBlack[i][j] = prefixBlack[i - 1][j] + prefixBlack[i][j - 1] - prefixBlack[i - 1][j - 1] + grid[i - 1][j - 1];
            prefixWhite[i][j] = prefixWhite[i - 1][j] + prefixWhite[i][j - 1] - prefixWhite[i - 1][j - 1] + (1 - grid[i - 1][j - 1]);
        }
    }
    
    int maxArea = 0;
    
    // 遍历所有可能的子矩形
    for (int top = 1; top <= n; ++top) {
        for (int bottom = top; bottom <= n; ++bottom) {
            unordered_map<int, int> diffMap;
            diffMap[0] = -1;  // 初始化差值0的位置为-1,用于处理全白的矩形
            int currDiff = 0;
            for (int r = 1; r <= m; ++r) {
                currDiff = prefixBlack[bottom][r] - prefixBlack[top - 1][r] - (prefixWhite[bottom][r] - prefixWhite[top - 1][r]);
                if (diffMap.find(currDiff) != diffMap.end()) {
                    int height = bottom - top + 1;
                    int width = r - diffMap[currDiff] - 1;
                    maxArea = max(maxArea, height * width);
                }
                diffMap[currDiff] = r;
            }
        }
    }
    
    cout << maxArea << endl;
    
    return 0;
}

请求大佬看一下我哪里错了?求助!!!

2024/12/1 15:45
加载中...