Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Iterate over the adjacent elements in a matix container

Reply
Thread Tools

Iterate over the adjacent elements in a matix container

 
 
Alexander
Guest
Posts: n/a
 
      09-26-2011
Hello everyone!

I need a way to perform an action in adjacent positions in a matrix (grid) container.

Example 1:
In a Minesweeper game, if a square is empty and there are no mines around it, all the empty squares around it should be opened, and all the empty squares around them, and ... well, you get the point.

Example 2:
In a painting program, when a 'fill' tool is used, when a pixel is clicked, all the adjacent squares, and their, adjacent squares, and... with the same color get colored in another way.

Could you tell me about a possibly simple, possibly efficient (emphasis on simplicity though) for implementing stuff like that?

If I haven't made myself clear enough, or you have any questions, please ask!

Thank you!

P.S. 1:
Sorry for posting to this group, this is not a c++ specific question, but I did not find a more suitable group, and I usually program in C++ (though recently I'm falling in love with Python for the quick-and-dirty jobs)

P.S. 2:
In case you think I'm a student asking help for his homework, I would be perfectly happy with general answers, like just the name of an algorithm. Anyway that's not the case. (I am a student, but in high-school, programming is a hobby for me).
 
Reply With Quote
 
 
 
 
Victor Bazarov
Guest
Posts: n/a
 
      09-26-2011
On 9/26/2011 3:44 PM, Alexander wrote:
> I need a way to perform an action in adjacent positions in a matrix
> (grid) container. [..]
>
> P.S. 1: Sorry for posting to this group, this is not a c++ specific
> question, but I did not find a more suitable group, and I usually
> program in C++ (though recently I'm falling in love with Python for
> the quick-and-dirty jobs)


Try comp.programming.

>[..]


V
--
I do not respond to top-posted replies, please don't ask
 
Reply With Quote
 
 
 
 
puppi
Guest
Posts: n/a
 
      09-26-2011
On Sep 26, 4:44*pm, Alexander <(E-Mail Removed)> wrote:
> Hello everyone!
>
> I need a way to perform an action in adjacent positions in a matrix (grid) container.
>
> Example 1:
> In a Minesweeper game, if a square is empty and there are no mines aroundit, all the empty squares around it should be opened, and all the empty squares around them, and ... well, you get the point.
>
> Example 2:
> In a painting program, when a 'fill' tool is used, when a pixel is clicked, all the adjacent squares, and their, adjacent squares, and... with the same color get colored in another way.
>
> Could you tell me about a possibly simple, possibly efficient (emphasis on simplicity though) for implementing stuff like that?
>
> If I haven't made myself clear enough, or you have any questions, please ask!
>
> Thank you!
>
> P.S. 1:
> Sorry for posting to this group, this is not a c++ specific question, butI did not find a more suitable group, and I usually program in C++ (thoughrecently I'm falling in love with Python for the quick-and-dirty jobs)
>
> P.S. 2:
> In case you think I'm a student asking help for his homework, I would be perfectly happy with general answers, like just the name of an algorithm. Anyway that's not the case. (I am a student, but in high-school, programmingis a hobby for me).


Try a stack. Or, if you really favor bits of simplicity over
efficiency, try recursion.
 
Reply With Quote
 
Juha Nieminen
Guest
Posts: n/a
 
      09-27-2011
Paul <(E-Mail Removed)> wrote:
> You could create two temp bool arrays of the same size.
> One array indicates the checked squares as a 1 value, set the equivalent
> index for the original square clicked on.
> Start a loop which tests each of the four squares adjacent to *the
> square*( starting with the square the user clicked as *the square*).
> Test each adjacent index for equality(see note) , update the other bool
> array to indicate which indices tested true.
> Test one bool array against the other for an xor result.
> If a true xor result is found then loop again[1] using the index that tested
> true(xor test) as *the square*, if not end.
> [1]Update the array that stores the tested squares to include the previous
> *square* before relooping.


As usual, you have no idea what you are talking about.

What he wants is a depth-first search, which is relatively simple recursive
algorithm:

1) Make a function that takes the initial point to be marked as parameter.

2) Mark that point.

3) Call this function recursively with each point adjacent to that one
which is empty (ie. to be included in the search) and not marked already.

The algorithm will naturally terminate when all the connected empty points
have been marked.
 
Reply With Quote
 
Krice
Guest
Posts: n/a
 
      09-27-2011
On 26 syys, 22:44, Alexander <(E-Mail Removed)> wrote:
> Example 2:
> In a painting program, when a 'fill' tool is used, when a pixel is
> clicked, all the adjacent squares, and their, adjacent squares, and..
> with the same color get colored in another way.


If you do some homework with google you'll find out that the routine
is called flood fill. The easiest way to implement it is scan over
the entire area with a seed number set to the point of origin:
surrounding to-be-filled spaces get new seed number and those points
are then processed in the next scan etc. until no more free spaces.
Then you have a seed map which is the shape of the area.
 
Reply With Quote
 
Richard Damon
Guest
Posts: n/a
 
      09-27-2011
On 9/27/11 3:12 AM, Juha Nieminen wrote:
> Paul<(E-Mail Removed)> wrote:
>> You could create two temp bool arrays of the same size.
>> One array indicates the checked squares as a 1 value, set the equivalent
>> index for the original square clicked on.
>> Start a loop which tests each of the four squares adjacent to *the
>> square*( starting with the square the user clicked as *the square*).
>> Test each adjacent index for equality(see note) , update the other bool
>> array to indicate which indices tested true.
>> Test one bool array against the other for an xor result.
>> If a true xor result is found then loop again[1] using the index that tested
>> true(xor test) as *the square*, if not end.
>> [1]Update the array that stores the tested squares to include the previous
>> *square* before relooping.

>
> As usual, you have no idea what you are talking about.
>
> What he wants is a depth-first search, which is relatively simple recursive
> algorithm:
>
> 1) Make a function that takes the initial point to be marked as parameter.
>
> 2) Mark that point.
>
> 3) Call this function recursively with each point adjacent to that one
> which is empty (ie. to be included in the search) and not marked already.
>
> The algorithm will naturally terminate when all the connected empty points
> have been marked.


One problem with a depth-first search done this way is you will need a
recursion depth equal to the maximum number of nodes that may need to be
marked. A breadth first search, using a stack like structure to store
the list of nodes to visit, may require less levels stored, and if using
tail recursion optimization, doesn't actually need to use recursion.

Pauls method is basically this except stores the locations to check in a
bit map, and scans the bit map to find the next location, which is
really neither breadth first or depth first. His method always uses 2
bits per cell in the universe, and a lot of program looping to scan. A
breadth first search needs to store a coordinate (maybe a 16 bit value
for up to a 256x256 pattern), and typically needs a lot less of them. It
also doesn't need to search to find the next point, so has a significant
time savings for a possible small space cost.
 
Reply With Quote
 
Juha Nieminen
Guest
Posts: n/a
 
      09-27-2011
Richard Damon <(E-Mail Removed)> wrote:
> One problem with a depth-first search done this way is you will need a
> recursion depth equal to the maximum number of nodes that may need to be
> marked. A breadth first search, using a stack like structure to store
> the list of nodes to visit, may require less levels stored, and if using
> tail recursion optimization, doesn't actually need to use recursion.


Well, the original poster emphasized simplicity, and the depth-first
search is definitely a very simple solution.

A minor optimization can be done to the solution I suggested: The function
also marks all the adjacent points (before making the recursive calls).
This may in some cases somewhat reduce the recursion depth (and overall
amount of work) performed compared to the pure depth-first search, and
isn't significantly more complicated to implement.
 
Reply With Quote
 
Alexander
Guest
Posts: n/a
 
      09-29-2011
Krice, thank you very much! The name of the algorithm I need helps very much i finding info.

Paul, sorry, but I'll need about a week to fully understand your idea.

Thanks everyone!
 
Reply With Quote
 
Juha Nieminen
Guest
Posts: n/a
 
      09-30-2011
Alexander <(E-Mail Removed)> wrote:
> Paul, sorry, but I'll need about a week to fully understand your idea.


Just curious, but I'm wondering if/why you consider the depth-first
search solution unfit.
 
Reply With Quote
 
Juha Nieminen
Guest
Posts: n/a
 
      09-30-2011
Richard Damon <(E-Mail Removed)> wrote:
> One problem with a depth-first search done this way is you will need a
> recursion depth equal to the maximum number of nodes that may need to be
> marked. A breadth first search, using a stack like structure to store
> the list of nodes to visit, may require less levels stored, and if using
> tail recursion optimization, doesn't actually need to use recursion.


Btw, I didn't notice this at first, but now I see that you seem to be
suggesting that it's much preferable to avoid recursion, even if it means
using a more complicated (to implement) solution. Why?

Note that by using a stack you are not really saving any memory. You
will still be storing O(n) amount of data (where n is the number of nodes
that have to be marked). In fact, depending a bit on the situation, the
breadth-first search may end up storing more data than the depth-first
search (although it's true that in some cases it may be the other way
around).

Anyways, your concern seems to not be the amount of data needed to
perform the task, but the recursion. Why? What exactly is the problem?
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
number of distinct elements in a const container and iterating over the distinct elements Hicham Mouline C++ 1 04-11-2010 10:56 AM
2 dimensional parity matix, pattern qty? Trs80 Cisco 0 06-21-2009 02:06 AM
How do you iterate over a List and remove elements? Knute Johnson Java 16 08-31-2007 05:28 AM
freeing a matix Michael Goerz C Programming 10 12-04-2006 06:41 AM
Copy elements from one STL container to another STL container Marko.Cain.23@gmail.com C++ 4 02-16-2006 05:03 PM



Advertisments