c++ - ACM图像压缩算法C++

Question

我一直在努力提高 C++ 的水平，所以我一直在解决为编程竞赛设计的问题。几天前我开始了这个问题，并且无法终生解决。我的算法以及如何修复它需要一些帮助。这是问题所在:ACM Image Compression problem

我的代码:我在下面进行了解释。

#include "Compress.h"
using namespace std;

Compress::Compress(){
    size = 0, threshold = 0, nRows=0, nCols=0;
    // Enter in a file name
    cout << "Welcome. Please type in the name of the file to read the numbers.\n";
    cin >> readFileName;

    inFile.open(readFileName.c_str());
    if(!inFile.is_open()) {
        cout << "Failed to open the file! Press Enter to exit..." << endl;
        exit(1);
    }

    //Finding the array size and threshold
    inFile >> size >> threshold;

    nRows = size;
    nCols = size;
    topright = size;
    bottomleft = size;

    //Let's make the array
    // creating the columns
    compressArray = new int* [nCols];

    // creating the rows
    for (int r = 0; r < nRows; r++){
        compressArray[r] = new int[nRows];
    }

    // FIll the array
    for (int i = 0; i < nRows; i++){
        for (int j = 0; j < nCols; j++){
            inFile >> compressArray[i][j];
        }
    }

    inFile.close();

    // Show before editing.
    print();
    work(0, nRows, 0, nCols);

}
Compress::~Compress(){
    for (int i = 0; i < nRows; i ++){
        delete compressArray[i];
    }
    delete [] compressArray;
}


void Compress::work(int start_x, int end_x, int start_y, int end_y){
    int nb_blacks = 0;
    int nb_whites = 0;
    int total_blocks = 0;
    int majority = 0;
    int percent = 0;

     cout << start_x << end_x << start_y << end_y << "\n------\n";

    for(int i = start_x; i < end_x; i++){
        for(int j = start_y; j < end_y; j++){
            if(compressArray[i][j] == 1){
                nb_blacks++;
            }
        }
    }

    total_blocks = ((end_x - start_x) * (end_y - start_y));
    nb_whites = total_blocks - nb_blacks;

    // give the max back
    majority = max(nb_blacks, nb_whites);
    // find the percent of the highest amount of colored blocks.
    percent = ((majority*100)/total_blocks);

    cout << "\n----\nPercent: " << percent << " Threshold: " << threshold  << endl;



    // majority/total_blocks is determining the percent of the greater
    // color in the box. We are comparing it to the threshold percent.
    if (percent >= threshold){
        for(int i = start_x; i < end_x; i++){
            for(int j = start_y; j < end_y; j++){
                if(nb_blacks > nb_whites) compressArray[i][j] = 1;
                else compressArray[i][j] = 0;
            }
        }
    }
    else {
            topright = topright/2;
            bottomleft = bottomleft/2;

            work(start_x, (end_x/2), (topright), end_y);
            work(start_x, (end_x/2), start_y, (end_y/2));
            work((bottomleft), end_x, start_y, (end_y/2));
            work((bottomleft), end_x, (topright), end_y);

    }

}

void Compress::print(){
    for (int r = 0; r < nRows; r++){
        for (int c = 0; c < nCols; c++){
            cout << compressArray[r][c];
        }
        cout << endl;
    }
}

因此，我的程序所做的是计算图像中黑色方 block 的数量(1 个)。然后将其与白色方 block (0)的数量进行比较。以较大者为准，根据图像中的方 block 数量转换为百分比。它将它与阈值进行比较。如果阈值小于百分比......整个图像变成了多数颜色。

如果阈值更高...它分成四个递归部分并放大。它将从右上角开始，然后是左上角、左下角和右下角。

我的程序适用于 4 x 4 的正方形，因为它可以正确地分成四个部分。然而，对于 8 x 8 的正方形...如果需要将其分成小于四个部分，一切都会变得一团糟。

我知道它为什么这样做。我放大递归函数的算法是错误的。如果正方形是 8 x 8...参数将类似于

0, 8, 0, 8 = looking at the whole square

0, 4, 4, 8 = the top right

corner using a 4 by 4 0, 2, 6, 8 = looking at the smallest top right

square of a 2 by 2.

我只是不知道可以满足我需要的数学函数。我不知道如何为 8 x 8 的正方形解决这个问题。我的代码甚至可以修复吗？或者我需要想出另一种方法吗？如果是，怎么办？

谢谢

Answer 1

修复了!数学函数只是一种痛苦。

标题函数

#include<cstdlib>
#include<iostream>
#include<string>
#include<fstream>


using namespace std;

class Compress{
    public:
        Compress();
        ~Compress();
        void input();
        void work(int start_x, int end_x, int start_y, int end_y);
        void print();

    private:
        int size;
        int threshold;
        int** compressArray;
        int nRows, nCols;

        string readFileName;
        ifstream inFile;
};

CPP 文件

#include "Compress.h"
using namespace std;

Compress::Compress(){
    size = 0, threshold = 0, nRows=0, nCols=0;
    // Enter in a file name
    cout << "Welcome. Please type in the name of the file to read the numbers.\n";
    cin >> readFileName;

    // Open the file.
    inFile.open(readFileName.c_str());
    if(!inFile.is_open()) {
        cout << "Failed to open the file! Press Enter to exit..." << endl;
        exit(1);
    }

    //Finding the array size and threshold
    inFile >> size;

    nRows = size;
    nCols = size;

    // Enter a threshold.
    cout << "Enter the desired threshold between 50-100: ";
    cin >> threshold;

    // Keep asking for the desired threshold until it is given.
    while (threshold < 50 || threshold > 100){
        cout << "\nIncorrect Threshold.\n";
        cout << "Enter the desired threshold between 50-100: ";
        cin >> threshold;
    }


    //Let's make the array
    // creating the columns
    compressArray = new int* [nCols];

    // creating the rows
    for (int r = 0; r < nRows; r++){
        compressArray[r] = new int[nCols];
    }

    // FIll the array
    for (int i = 0; i < nRows; i++){
        for (int j = 0; j < nCols; j++){
            inFile >> compressArray[i][j];
        }
    }

    inFile.close();

    // Show before editing.
    print();
    work(0, nRows, 0, nCols);

}
Compress::~Compress(){
    for (int i = 0; i < nRows; i ++){
        delete compressArray[i];
    }
    delete [] compressArray;
}


void Compress::work(int start_x, int end_x, int start_y, int end_y){
    int Size = end_y - start_y; // Finding the midpoints.
    int nb_blacks = 0;
    int nb_whites = 0;
    int total_blocks = 0;
    int majority = 0;
    int percent = 0;

//    Testing everything.

//    cout << "\nx1, y1: " << start_x << "," << start_y << " x2,y2: " << end_x << "," << end_y << endl;
//    for (int r = start_x; r < end_x; r++){
//        for (int c = start_y; c < end_y; c++){
//            cout << compressArray[r][c];
//        }
//        cout << endl;
//    }

    // Initial case. If 1, break and start returning results
    if (end_x <= start_x || end_y <= start_y){
        return;
    }

   //  Keep breaking it down until it reaches 1.
    else {
        // Count the Number of Black pieces
        for(int i = start_x; i < end_x; i++){
            for(int j = start_y; j < end_y; j++){
                if(compressArray[i][j] == 1){
                    nb_blacks++;
                }
            }
        }

        // Find the total and number of white pieces.
        total_blocks = ((end_x - start_x) * (end_y - start_y));
        nb_whites = total_blocks - nb_blacks;

        // give the max back
        majority = max(nb_blacks, nb_whites);
        // find the percent of the highest amount of colored blocks.
        percent = ((majority*100)/total_blocks);

//        cout << "Percent: " << percent << " Threshold: " << threshold  << "\n-----\n";


        // majority/total_blocks is determining the percent of the greater
        // color in the box. We are comparing it to the threshold percent.
        if (percent >= threshold){
            for(int i = start_x; i < end_x; i++){
                for(int j = start_y; j < end_y; j++){
                    if(nb_blacks > nb_whites) compressArray[i][j] = 1;
                    else compressArray[i][j] = 0;
                }
            }
        }

        // Keep breaking down until we reach the initial case.
        else {
            work((end_x - (Size/2)), (end_x), (start_y), (start_y + (Size/2)));
            work(start_x, (start_x + (Size/2)), (start_y), (start_y + (Size/2)));
            work((start_x), (start_x + (Size/2)), (end_y - (Size/2)), end_y);
            work((end_x - (Size/2)), end_x, (end_y - (Size/2)), end_y);
//
//            work((start_x), (mid_x), (mid_y), end_y);
//            work(start_x, (mid_x ), (start_y), (mid_y));
//            work((mid_x), end_x, start_y, (mid_y));
//            work((mid_x), end_x, (mid_y), end_y);
        }
    }
}

void Compress::print(){

    // Print the function
    cout << "\nImage: " << threshold << "%\n";
    for (int r = 0; r < nRows; r++){
        for (int c = 0; c < nCols; c++){
            cout << compressArray[r][c];
        }
        cout << endl;
    }
}