Playing with recursion | C++



Hey there! Welcome back.
Today I had a very interesting problem in my mind and I tried to solve it with recursion.

The problem statement is:

Given a matrix with each of its cell having a categorical value, your task is to delete/remove all duplicate values in connected cells. Here the connected cells are the horizontal and vertical cells (can be diagonal as well).
Here is my solution in C++

#include<bits/stdc++.h>
#define N 5
#define NN 10
using namespace std;
string colorArr[NN] = {"RED","BLUE","GREEN","YELLOW","PINK","ORANGE","PURPLE","BROWN","BLACK","WHITE"};
void init(vector<vector<string>>&vec){
srand(time(NULL));
for(int i=0;i<vec.size();i++){
for(int j=0;j<vec[0].size();j++){
vec[i][j] = colorArr[rand()%4]; /* Change value to change color occurences */
}
}
}
void printMatrix(vector<vector<string>>&vec){
for(int i=0;i<vec.size();i++){
for(int j=0;j<vec[0].size();j++){
if(vec[i][j]!="")
cout << vec[i][j] << "\t";
else
cout << "*\t";
}
cout << endl;
}
cout << endl;
}
void recursiveDiffusion(vector<vector<string>>&vec,string ch,int x,int y){
if(x<0||y<0||x>=N||y>=N)
return;
if(vec[x][y]==ch){
vec[x][y]="";
recursiveDiffusion(vec,ch,x-1,y);
recursiveDiffusion(vec,ch,x+1,y);
recursiveDiffusion(vec,ch,x,y-1);
recursiveDiffusion(vec,ch,x,y+1);
/*//Diagonals
recursiveDiffusion(vec,ch,x+1,y+1);
recursiveDiffusion(vec,ch,x-1,y+1);
recursiveDiffusion(vec,ch,x+1,y-1);
recursiveDiffusion(vec,ch,x-1,y-1);*/
}
}
void printColorInfo(vector<vector<string>>&vec){
int totalColorGroups = 0;
for(int i=0;i<vec.size();i++){
for(int j=0;j<vec[0].size();j++){
if(vec[i][j]!=""){
/* cout << "Color: " << vec[i][j] << " Loc: " << i << ", " << j << endl;*/
string temp = vec[i][j];
recursiveDiffusion(vec,vec[i][j],i,j);
totalColorGroups++;
vec[i][j]=temp;
}
}
}
/*cout << "\n Total Color Groups Found: " << totalColorGroups << endl;*/
}
void printLine(){
for(int i=0;i<80;i++)
cout << "+";
cout << endl;
}
int main(){
vector<vector<string>>vec(N,vector<string>(N,""));
init(vec);
printMatrix(vec);
//printLine();
printColorInfo(vec);
printLine();
printMatrix(vec);
return 0;
}


OUTPUT:

GREEN YELLOW GREEN YELLOW YELLOW
GREEN RED YELLOW GREEN RED
GREEN YELLOW GREEN BLUE BLUE
GREEN GREEN YELLOW GREEN YELLOW
BLUE GREEN RED YELLOW GREEN

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
GREEN YELLOW GREEN YELLOW *
* RED YELLOW GREEN RED
* YELLOW GREEN BLUE *
* * YELLOW GREEN YELLOW
BLUE * RED YELLOW GREEN

Suhaib Bin Younis | @suhaibbinyounis

Post a Comment

Post a Comment (0)

Previous Post Next Post