Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #10546

Re: Iterate over the adjacent elements in a matix container

Show all headers | View raw

On 9/27/11 3:12 AM, Juha Nieminen wrote:
> Paul<pchristor@yahoo.co.uk>  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.

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Iterate over the adjacent elements in a matix container Alexander <alvatov@gmail.com> - 2011-09-26 12:44 -0700
  Re: Iterate over the adjacent elements in a matix container Victor Bazarov <v.bazarov@comcast.invalid> - 2011-09-26 15:49 -0400
  Re: Iterate over the adjacent elements in a matix container puppi <fabricio.puppi@gmail.com> - 2011-09-26 15:30 -0700
  Re: Iterate over the adjacent elements in a matix container "Paul" <pchristor@yahoo.co.uk> - 2011-09-27 06:43 +0100
    Re: Iterate over the adjacent elements in a matix container Juha Nieminen <nospam@thanks.invalid> - 2011-09-27 07:12 +0000
      Re: Iterate over the adjacent elements in a matix container Richard Damon <news.x.richarddamon@xoxy.net> - 2011-09-27 11:10 -0400
        Re: Iterate over the adjacent elements in a matix container Juha Nieminen <nospam@thanks.invalid> - 2011-09-27 20:32 +0000
        Re: Iterate over the adjacent elements in a matix container Juha Nieminen <nospam@thanks.invalid> - 2011-09-30 06:24 +0000
          Re: Iterate over the adjacent elements in a matix container Nobody <nobody@nowhere.com> - 2011-09-30 20:55 +0100
          Re: Iterate over the adjacent elements in a matix container Richard Damon <news.x.richarddamon@xoxy.net> - 2011-09-30 17:07 -0400
  Re: Iterate over the adjacent elements in a matix container Krice <paulkp@mbnet.fi> - 2011-09-27 03:37 -0700
  Re: Iterate over the adjacent elements in a matix container Alexander <alvatov@gmail.com> - 2011-09-29 10:47 -0700
    Re: Iterate over the adjacent elements in a matix container "Paul" <pchristor@yahoo.co.uk> - 2011-09-30 01:28 +0100
    Re: Iterate over the adjacent elements in a matix container Juha Nieminen <nospam@thanks.invalid> - 2011-09-30 06:19 +0000
    Re: Iterate over the adjacent elements in a matix container "Paul" <pchristor@yahoo.co.uk> - 2011-10-02 05:16 +0100
      Re: Iterate over the adjacent elements in a matix container "Paul" <pchrist<nospam>or@yahoo.co.uk> - 2011-10-03 05:31 +0100
        Re: Iterate over the adjacent elements in a matix container "Paul" <pchrist<nospam>or@yahoo.co.uk> - 2011-10-03 05:47 +0100

csiph-web