Подсчет элемента в матрице с использованием Divide & amp; Завоевать

Question

Подсчет элемента в матрице с использованием Divide & amp; Завоевать

Я начинаю учиться реализовывать алгоритмы «разделяй и властвуй», но у меня возникли некоторые проблемы с этим упражнением.

Я написал алгоритм, но, к сожалению, он возвращает значение 0. Мне нужно посчитать, сколько раз число находит в матрице, используя D&C.

Моя идея состоит в том, чтобы разделить матрицу на 4 подматрицы, пока все координаты не будут равны, это означает, что есть элемент (может быть мой номер или нет).

Мои сокращения:

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

Когда я компилирую, он работает хорошо, но возвращает 0 (из-за моего заявления о прекращении я думаю). Итак, моя ошибка в функции solve ().

Мой код:

#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;
}

Может быть, вы можете сказать мне, где проблема, или напрямую решить ее, это было бы быстрее, и я могу понять легче.

-1

algorithm c++divide-and-conquer matrix

Решение

Другие решения

Рекурсия не обновляет 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
}

0

Источник

Accepted Answer

Вот исправленный исходный код. Я добавил несколько комментариев, чтобы вы могли следить за ним. Кроме того, я переключился на динамический массив правильного размера.

#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;
}

Помните, что это чисто образовательный пример. В реальном мире никто бы не посчитал подобные явления.

0