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

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

Re: Iterate over the adjacent elements in a matix container

Show all headers | View raw

"Alexander" <alvatov@gmail.com> wrote in message 
news:13318117.2085.1317066256036.JavaMail.geo-discussion-forums@yqmw31...
> 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).

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.

Note:
Every time you test an index for equality you first need to make sure that 
index is in bounds:

Suppose a 1d array of size 5 like so:
00001
If we start with index4 and test the 2 adjacents, index 5 would be out of 
bounds, so before you test the adjacent squares you first need to test if 
there is an adjacent square.
One thing you can do is make the array oversized so it doesn't matter if you 
go over bounds by one i.e: Create an array of size 7 and offset it by +1.
0000010

int my_array[7] = {0};
int* p_arr = my_array;
++p_arr;

p_arr[-1] =who_cares_whats_there;
p_arr[5] = who_cares_whats_there;

The bool arrays do not need to be oversized so *the square* will always have 
a one square buffer due to the oversized array. This can be applied to a 2d 
array too.


HTH
Paul. 


--- Posted via news://freenews.netfront.net/ - Complaints to news@netfront.net ---

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