Count of an element in a matrix using Divide & Conquer

Question

I'm starting to learn how to implement divide and conquer algorithms, but I'm having some trouble with this exercise.

I have written an algorithm but unfortunately it returns a 0 value. I need to count how many times a number finds in the matrix using D&C.

My idea is to divide the matrix in 4 sub-matrices till all coordinates are equal, it means that there is an element (could be my number or not).

My abbreviations:

lr - left row   | starting with 
lc- left column | left lower corner
rr - right row    | starting with
rc- right column  |  right upper corner

When I compile, it runs well but returns 0 (because of my stop statement I think). So, my error is in solve() function.

My code:

#include<fstream>
#include<conio.h>
#include<iostream>
using namespace std;
ifstream fin("in.txt");
#define debug cerr<<"OK";
int n,a[100][100];
int solve(int lr,int lc, int rr,int rc,int x,int &contor)
{
    int cnt=0;
    if(lr < rr || lc > rc)
    {
        if(cnt<=0)
            return 0;
        return cnt;
    }
        if(lr == lc && rr == rc)
        if(a[lr][lc] == x)
            cnt++;
        else;
    else
    {
        int l=(lr+rr)/2;
        int c=(lc+rc)/2;
        if(l && c)
        {
        int cnt1=solve(lr-l,lc,rr,rc-c,x,contor); // coordinates for upper left square
        int cnt2=solve(lr-l,lc+c,rr,rc,x,contor); // -||- for upper right square
        int cnt3=solve(lr,lc,rr+l,rc-c,x,contor); // -||- for low left square 
        int cnt4=solve(lr,lc+c,rr,rc-c,x,contor); // -||- for low right square
        contor=cnt1+cnt2+cnt3+cnt4;
        }
    }
}

int main()
{  
    fin>>n;
    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        fin>>a[i][j];
    int contor=0;
solve(n,1,1,n,3,contor);  // i'm searching for 3
   cout<<contor;
    _getch();
   fin.close();
   return 0;
}

Maybe you can tell me where the problem is or directly solve it, it would be faster and I can understand easier.

Input:
4
1 3 3 4
5 6 7 8
1 2 3 4
4 3 2 1

Answer 1

Here is the corrected source code. I have added some comments so you can follow it. Furthermore, I switched to a dynamic array of the correct size.

#include<fstream>
#include<conio.h>
#include<iostream>

using namespace std;

int countOccurences(int** values, int min1, int min2, int max1, int max2, int searchValue)
{
    if (min1 > max1 || min2 > max2)
        return 0; //invalid area

    if (min1 == max1 && min2 == max2)
    {
        //the current area is a single cell
        if (values[min1][min2] == searchValue)
            return 1; //we have found 1 occurence
        else
            return 0; //we have found nothing
    }
    else
    {
        //divide the current range
        int center1 = (min1 + max1) / 2;
        int center2 = (min2 + max2) / 2;

        int occurencesInSubMatrices = 0;

        //accumulate the occurences in the according variable
        occurencesInSubMatrices += countOccurences(values, min1, min2, center1, center2, searchValue); // coordinates for upper left square
        occurencesInSubMatrices += countOccurences(values, center1 + 1, min2, max1, center2, searchValue); // -||- for upper right square
        occurencesInSubMatrices += countOccurences(values, min1, center2 + 1, center1, max2, searchValue); // -||- for low left square 
        occurencesInSubMatrices += countOccurences(values, center1 + 1, center2 + 1, max1, max2, searchValue); // -||- for low right square
        return occurencesInSubMatrices;
    }
}

int main()
{
    ifstream fin("in.txt");
    int n;
    fin >> n;

    //create a 2d array of appropriate size
    int** values = new int*[n];

    for (int i = 0; i < n; i++)
    {
        //allocate memory for the i-th row
        values[i] = new int[n];
        for (int j = 0; j < n; j++)
            fin >> values[i][j];
    }

    int count = countOccurences(values, 0, 0, n - 1, n - 1, 3);  // i'm searching for 3
    cout << count;
    _getch();
    fin.close();
    return 0;
}

Please be aware that this is a purely educational example. In the real world, nobody would count ocurrences like this.

Answer 2

Recursion does not update cnt...

    if(l && c)
    {
    solve(lr-l,lc,rr,rc-c,x); // coordinates for upper left square 
    solve(lr-l,lc+c,rr,rc,x); // -||- for upper right square
    solve(lr,lc,rr+l,rc-c,x); // -||- for low left square 
    solve(lr,lc+c,rr,rc-c,x); // -||- for low right square
    }