Making an Origami (Divide and Conquer Algorithm)

 This Problem was introduced on the BackJoon Algorithm Website.

Problem :

    Cutting a paper to make sure each of the small and big squares is in the same color (blue or white).

The basic rule for cutting a paper is following:

1.      If all the parts in the paper are not the same color, cut the paper into 4 squares of the same size. 

    2. Continue doing rule #1 until all the squares are in the same color.

I used the divide and conquer Algorithm.

The "Divide" function calls itself recursively until the paper is following the rule.

Once the width and the height of the paper are 1, it stops and adds count to the color of itself.

A better way of solving this problem is, without actually creating the vector every time calling the "Divide" function, just change the start and the end index of the function and pass them to the "Divide" function.

Code (C++) :

#include <iostream>

#include <math.h> 

#include <algorithm>

#include <vector>

using namespace std;

int cntWhite = 0;

int cntBlack = 0;

void Divide(vector<vector<int>> vecParts) {

if (vecParts.size() == 1) {

if (vecParts[0][0] == 1) {

cntWhite++;

}

else {

cntBlack++;

}

return;

}

bool checkSame = true;

int firstColor = vecParts[0][0];

for (int i = 0; i < vecParts.size(); i++) {

if (checkSame == false)break;

for (int k = 0; k < vecParts.size(); k++) {

if (firstColor != vecParts[i][k]) {

checkSame = false;

break;

}

}

}

if (checkSame == true) {

if (vecParts[0][0] == 1) {

cntWhite++;

}

else {

cntBlack++;

}

}

else {

for (int w = 0; w < 4; w++) {

int size1 = 0;

int end1 = 0;

int size2 = 0;

int end2 = 0;

if (w == 0) {

size1 = 0;

end1 = vecParts.size() / 2;

size2 = 0;

end2 = vecParts.size() / 2;

}

else if (w == 1) {

size1 = vecParts.size() / 2;

end1 = vecParts.size();

size2 = 0;

end2 = vecParts.size() / 2;

}

else if (w == 2) {

size1 = 0;

end1 = vecParts.size() / 2;

size2 = vecParts.size() / 2;

end2 = vecParts.size();

}

else if(w == 3) {

size1 = vecParts.size() / 2;

end1 = vecParts.size();

size2 = vecParts.size() / 2;

end2 = vecParts.size();

}

vector<vector<int>> vecAll;

for (int i = size1; i < end1; i++) {

vector<int> vecTemp;

for (int k = size2; k < end2; k++) {

vecTemp.push_back(vecParts[i][k]);

}

vecAll.push_back(vecTemp);

}

Divide(vecAll);

}

return;

}

}

int main()

{

int N;

cin >> N;

vector<vector<int>> vecAll;

for (int i = 0; i < N; i++) {

vector<int> vecTemp;

for (int k = 0; k < N; k++) {

int temp;

cin >> temp;

vecTemp.push_back(temp);

}

vecAll.push_back(vecTemp);

}

Divide(vecAll);

cout << cntBlack << endl;

cout << cntWhite << endl;

}

Problem Source: https://www.acmicpc.net/problem/2630

My Github:  https://github.com/AdvancedUno/AlgorithmProblems/tree/main/Divide_and_Conquer/Divide_and_Conquer