title: ACM Image Compression Algorithm C++
body: <p>I've been trying to get better at c++, so I've been solving problems designed for programming contests. I started this problem a few days ago, and cannot solve it for the life of me. I need some help with my algorithm and how to fix it. This is the problem: <a href="https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=404&amp;page=show_problem&amp;problem=2927" rel="nofollow">ACM Image Compression problem</a></p>
  
  <p><strong>MY CODE:</strong> I explain it underneath. </p>
  
  <pre><code>#include "Compress.h"
  using namespace std;
  
  Compress::Compress(){
      size = 0, threshold = 0, nRows=0, nCols=0;
      // Enter in a file name
      cout &lt;&lt; "Welcome. Please type in the name of the file to read the numbers.\n";
      cin &gt;&gt; readFileName;
  
      inFile.open(readFileName.c_str());
      if(!inFile.is_open()) {
          cout &lt;&lt; "Failed to open the file! Press Enter to exit..." &lt;&lt; endl;
          exit(1);
      }
  
      //Finding the array size and threshold
      inFile &gt;&gt; size &gt;&gt; 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 &lt; nRows; r++){
          compressArray[r] = new int[nRows];
      }
  
      // FIll the array
      for (int i = 0; i &lt; nRows; i++){
          for (int j = 0; j &lt; nCols; j++){
              inFile &gt;&gt; compressArray[i][j];
          }
      }
  
      inFile.close();
  
      // Show before editing.
      print();
      work(0, nRows, 0, nCols);
  
  }
  Compress::~Compress(){
      for (int i = 0; i &lt; 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 &lt;&lt; start_x &lt;&lt; end_x &lt;&lt; start_y &lt;&lt; end_y &lt;&lt; "\n------\n";
  
      for(int i = start_x; i &lt; end_x; i++){
          for(int j = start_y; j &lt; 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 &lt;&lt; "\n----\nPercent: " &lt;&lt; percent &lt;&lt; " Threshold: " &lt;&lt; threshold  &lt;&lt; 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 &gt;= threshold){
          for(int i = start_x; i &lt; end_x; i++){
              for(int j = start_y; j &lt; end_y; j++){
                  if(nb_blacks &gt; 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 &lt; nRows; r++){
          for (int c = 0; c &lt; nCols; c++){
              cout &lt;&lt; compressArray[r][c];
          }
          cout &lt;&lt; endl;
      }
  }
  </code></pre>
  
  <p>So, what my program does is count the number of black squares in the image (1's). It than compares it to the number of white squares (0's). Whichever is larger, is turned into a percent based on how many squares are in the image. It compares it with the threshold. If the threshold is smaller than the percent... The whole image turned the majority color. </p>
  
  <p>If the threshold is higher... It breaks into four recursive parts and zooms in. It will start with the top right, then top left, bottom left, and bottom right. </p>
  
  <p>My program works with a 4 by 4 square, because it breaks into four parts correctly. However, with the 8 by 8 square... if it needs to be broken into smaller than four parts, everything messes up. </p>
  
  <p>I know why it does this. My algorithm for zooming in the recursive function is wrong. If the square is an 8 by 8... the parameters would be something like</p>
  
  <blockquote>
    <p>0, 8, 0, 8 = looking at the whole square</p>
    
    <p>0, 4, 4, 8 = the top right</p>
    
    <p>corner using a 4 by 4 0, 2, 6, 8 = looking at the smallest top right</p>
    
    <p>square of a 2 by 2.</p>
  </blockquote>
  
  <p>I just don't know a mathematical function that would get what I need. I have no idea how to fix this for 8 by 8 squares. Is my code even possible to fix? Or do I need to figure out another way of going about it? If so, how?</p>
  
  <p>Thank you</p>