Search in 2d array using recursion

Question

3.00/5 (4 votes)

See more:

I need to implement a function that searches in the 2D Array using recursion.
For example, we have bool Array[10][10]. What is needed is to count how many bunch of True neighboring cells in the 2D Array.
I mean if x[1][1]== true && x[1][2]==true && x[0][3]==true and the cells around them are false then this the counter adds one.
This is like counting how many splash are on the floor

Thanks a lot.

Posted 15-Apr-11 8:33am

console_programing

Updated 15-Apr-11 10:19am

v3

Add a Solution

Comments

Sergey Alexandrovich Kryukov 15-Apr-11 14:51pm

Not only it's hard anyone to get interested in solving your homework problem, but it is not even formulated.
The mere fact that you do not realized the problem is not yet defined tells me that you're very far from success, and that getting any help from CodeProject does not look promising at all.

The extra requirement "using recursion" also does not look reasonable. You either ask for a solution or offer solution, not anywhere in between. Who cares what your teacher told you? If she/he needs the solution let her/him ask CodeProject herselt/himself.

--SA

OriginalGriff 15-Apr-11 14:55pm

Sorry SA! You hadn't posted your comment when I started my answer; if you had, I would have held off. It isn't a suitable target for recursion anyway: the children are not the same type as the parents!

#realJSOP 15-Apr-11 14:58pm

Seems like a natural pattern. I say that about my daughter all the time.

OriginalGriff 15-Apr-11 15:01pm

What? She doesn't like guns! :laugh:

Sergey Alexandrovich Kryukov 15-Apr-11 15:51pm

No problem.
I believe it could be possible to draw a recursive algorithm in some artificial way, it just does not seem adequate. Main thing is that the depth of recursion would grow too fast, such as N*N or so.
The problem is not yet defined, because it does not define a "block", in particular it is not defined what is a "neighboring cell".
--SA

console_programing 15-Apr-11 16:23pm

I dont need a solution for my question. Im not cheating I need an explanation of what should be done. And I think that I was wrong in explaining the the question mysteriously . Thanks anyway for your comment

Sergey Alexandrovich Kryukov 15-Apr-11 16:59pm

OK, thank you for understanding and confirmation of my guess. It still need a definition of a block and a neighboring cells.
--SA

5 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Sergey Alexandrovich Kryukov · Answer 1 · 2011-04-15T11:04:00

[Answer in response to clarification of the problem by OP]

What you need as a next step is correct definition of a neighbor. This is a usual step in Cell Automatons and related parts of Game Theory.

See on introduction on Cell Games: http://en.wikipedia.org/wiki/Cell_games_(cellular_automaton)[^].

For example, you can define a neighbor as a cell touching side-by-side, by corners (diagonally) or both, or some subset of these sets, or something else. Next step would be the definition of the block: a single sell or more, two or more or something else.

When you have it, it can solve a problem, more or less effectively. Not a very hard yet not completely trivial problem I, would say, a typical one in learning algorithms.

Good luck,

—SA

OriginalGriff · Answer 2 · 2011-04-15T08:53:00

Solution 2

How do you propose to do that with recursion? It's not a recursive structure, so iterration is a more natural approach. You can only recurse when the children are the same as the parent: A List containing a List, containing a List, for example. Your data is an array of (array of bool)s.

foreach (bool[] ar in Array)
   {
   foreach (bool b in ar)
      {
      if (b)
         {
         count++;
         }
      }
   }

Posted 15-Apr-11 8:53am

OriginalGriff

Comments

Sergey Alexandrovich Kryukov 15-Apr-11 15:58pm

I see. The answer would be correct if it is a total number of true values.
Maybe I overestimate the real problem, but I thought it is about "blocks" (as OP called then) which I thought would be clusters of somehow "close" true-valued cells. That would be some more essential problem. What do you think?
--SA

Sergey Alexandrovich Kryukov 15-Apr-11 17:07pm

OP just confirmed my understanding, please see my Answer.
--SA

web works · Answer 3 · 2011-04-15T08:53:00

You will have to use nested for loops. Try below code.
i have not tested this code.

int i, j, totalBoolCount = 0;
for(i=0;i<arr.Length;i++)
{
    for(j=0;j<arr[i].Length;j++)
    {
        if(arr[i][j] == true)
        {
            totalBoolCount++;
        }
    }
}
//print totalBoolCount here and see if it answers your question.

Good Luck

[edit]Please, try not to use Magic Numbers, particularly when talking to beginners. Using Array.Length in the outer loop and Array[i].Length in the inner makes it more likely they will not have problems when the array size changes to 5 by 8! (Oh, and initialize your variables! - OrignalGriff[/edit]

**Orcun Iyigun** · Answer 4 · 2011-04-15T08:59:00

First of all do you know how to iterate through one dimensional array? Because if you do so adding another dimension is not a big deal.

When you sort through an array basically you use arrayName[iterator] and iterate through the indexes and see if it is suitable for your condition or not.

Here you have as you mentioned Array[10][10] so you need to use 2 loops to iterate through. You man want to use 2 for loops one for the first dimension and the other for the second dimension. It doesnt matter which one is first.

Thats a hint for you.

For references check these links;

Link 1[^]
Link 2[^]

Link 1 has more details and give you a better understanding.

CPallini · Answer 5 · 2011-04-15T10:32:00

Solution 4

C#

static int true_count(bool [][] array, int i, int j, int count)
 {
     if (i == array.GetLength(0))
         return count;
     if (j == array[i].GetLength(0))
         return true_count(array, i + 1, 0, count);
      else
         return true_count(array, i, (j + 1), array[i][j] ? (count + 1) : count);
 }

usage example:

C#

bool [][] mybool = new bool[2][];
for (int i = 0; i < 2; i++)
    mybool[i] = new bool[3];

mybool[0][0] = true;
mybool[0][1] = true;
mybool[0][2] = false;

mybool[1][0] = true;
mybool[1][1] = false;
mybool[1][2] = true;

Console.WriteLine("Count = {0}", true_count(mybool, 0, 0, 0));

Posted 15-Apr-11 10:32am

CPallini

Comments

console_programing 15-Apr-11 16:37pm

Thanks a lot.

Sergey Alexandrovich Kryukov 15-Apr-11 17:08pm

It needs more or the definition of the problem before you can devise any algorithm.
OP just confirmed my understanding, please see my Answer.
--SA

CPallini 16-Apr-11 6:13am

Actually the original requirements were clear (howevere they weren't what the OP was looking for...) :-)

Sergey Alexandrovich Kryukov 16-Apr-11 14:28pm

Clear only if you assume most likely rules.
Thank you.
--SA

Search in 2d array using recursion

5 solutions

Solution 5

Solution 2

Solution 1

Solution 3

Solution 4

Add your solution here

Preview 0