Neigbour array elements

This is a discussion on Neigbour array elements within the C Programming forums, part of the General Programming Boards category; I'm dealing with 2 dimensional arrays and i couldn't figure out how to do this: for example assume we have ...

  1. #1
    Registered User
    Join Date
    Apr 2009
    Posts
    5

    Neigbour array elements

    I'm dealing with 2 dimensional arrays and i couldn't figure out how to do this:

    for example assume we have a 4x4 matrix, and there is a predefined number k(which is between 0 and 128).well let's declare the array as a[i][j]. for example if the value of a[i][j]>k and if the neigbours of a[i][j]<=k,it will count 1.
    but when a[i][j]>k , if one or more of a[i][j]'s neigbours is also bigger than k ,it will also count 1. I mean,for example if a[0][0]>k,a[0][1]>k and a[1][1]>k this whole 3 cell count as 1.
    how can i make this?

  2. #2
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Quote Originally Posted by ashley90 View Post
    I mean,for example if a[0][0]>k,a[0][1]>k and a[1][1]>k...
    Not sure about your requirements and by chance did you mean
    Code:
    a[0][0]>k, a[0][1]>k and a[1][0]>k
    Since a[1][0] comes before a[1][1] in relation to a[0][0].

  3. #3
    Registered User
    Join Date
    Apr 2009
    Posts
    5
    |0 |0 |0 |1 |0 |1 |
    |0 |1 |1 |1 |1 |0 |
    |0 |0 |1 |0 |0 |0 |
    |0 |0 |1 |1 |0 |0 |
    |0 |0 |0 |0 |0 |0 |

    for example in here the count will be 2. a[0][5] counts 1 because it has no neigbors with 1( bigger than k)(diagonal not counts). but from a[0][3] to other 1's below it, there is a path without entering a 0 cell. So all of it counts 1. and totally count=2.

    well i couldn't figure out how to find that kind of paths.

  4. #4
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Okay so I am confused about your requirements. State them as simply and clearly as possible and more than likely someone from the cboard will help out.

  5. #5
    Registered User
    Join Date
    Apr 2009
    Posts
    5
    Quote Originally Posted by itCbitC View Post
    Okay so I am confused about your requirements. State them as simply and clearly as possible and more than likely someone from the cboard will help out.
    Look, for example consider this 2x2 matrix:

    when

    1 0
    0 1 in here count=2 because we can't find a path between cell of 1's without entering a cell of 0

    1 1
    0 0 but in here count=1 because there is path between 1's without entering 0 cell and it counts 1

    it's obvious i guess. the same thing goes for the above matrix i gave.

  6. #6
    Registered User
    Join Date
    Aug 2008
    Posts
    129
    I probably won't be one of the ones helping with code, but...

    EDIT: Oh, never mind that post if you read it. You're counting the number of "continents," or contiguous blocks of cells >k, in the matrix.
    Last edited by Jesdisciple; 04-12-2009 at 08:13 PM.

  7. #7
    Registered User
    Join Date
    Apr 2006
    Posts
    2,027
    Do it out on paper. How would you count continents without the computer. Then, translate the algorithim you come up with into C.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  8. #8
    Registered User
    Join Date
    Apr 2009
    Posts
    5
    Quote Originally Posted by King Mir View Post
    Do it out on paper. How would you count continents without the computer. Then, translate the algorithim you come up with into C.
    Yeah i did it on paper but couldn't convert it to a code. For example i wrote first a function which gives 1 or 0 to cell according to their value and k. Then i tried to check every cell one by one. If it has no neigbor with 1's , its easy to convert to code but i couldn't do the second part which if a cell has a neigbor with 1 and also if this neigbor cell of 1 has neigbors with 1...

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by ashley90 View Post
    Look, for example consider this 2x2 matrix:

    when

    1 0
    0 1 in here count=2 because we can't find a path between cell of 1's without entering a cell of 0

    1 1
    0 0 but in here count=1 because there is path between 1's without entering 0 cell and it counts 1

    it's obvious i guess. the same thing goes for the above matrix i gave.
    In the
    1 0
    0 1 matrix, the count is 2 because you have two 1's that have no path to other cells, right?

    And in this matrix:
    1 1
    0 0
    the count is 1 because it has no path to the last row.

    If the matrix were:
    1 1
    0 0
    0 0
    then would the count be 2 (meaning we're counting the number of rows with no path to them), or would it be one, because we're counting the link(s) between two cells.

    What would these counts be?
    1 1
    0 1
    0 1

    1 1
    0 0
    1 1

    As we loop (iterate) through the loop, what *exactly* triggers a count increase? That's all we need to know. Your prior description was more of a pronouncement. "Count is N!"

    If you can "nail down" the description, of just exactly what we're counting, the problem will be solved in a jiffy. Then it's a trivial problem to code up.

  10. #10
    Registered User
    Join Date
    Apr 2009
    Posts
    5
    Quote Originally Posted by Adak View Post
    In the
    1 0
    0 1 matrix, the count is 2 because you have two 1's that have no path to other cells, right?

    And in this matrix:
    1 1
    0 0
    the count is 1 because it has no path to the last row.

    If the matrix were:
    1 1
    0 0
    0 0
    then would the count be 2 (meaning we're counting the number of rows with no path to them), or would it be one, because we're counting the link(s) between two cells.

    What would these counts be?
    1 1
    0 1
    0 1

    1 1
    0 0
    1 1

    As we loop (iterate) through the loop, what *exactly* triggers a count increase? That's all we need to know. Your prior description was more of a pronouncement. "Count is N!"

    If you can "nail down" the description, of just exactly what we're counting, the problem will be solved in a jiffy. Then it's a trivial problem to code up.
    Ok, i'll try to make it clear,

    1 1
    0 0
    0 0 in here count is 1. why? because there is path between them without entering 0 cell.

    1 1
    0 1
    0 1 in here count is again 1 since you can see the path through the 1's.

    1 1
    0 0
    1 1 in here count is 2 since 1 from the first row and 1 from the 3rd.

    another example

    1 1 1
    0 1 0
    1 1 1 in here count is again 1 because you can go through 1 cell's without entering 0's.

    i hope it makes sense now

  11. #11
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Ok, so the count is counting up every group of 1's in the matrix.

    Two isolated groups - count is 2
    One group all connected - count is 1

    The size of the group(s) doesn't matter, just how many distinct, separate groups there are.

    Now I see what you're saying! <light comes on>

  12. #12
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    This is what I had in mind. For ease of programming, I surrounded the "real" matrix, with a row of zero's on the top and bottom, and with a column of zero's, on either side.

    That's just to make the programming easier to avoid array out of bounds, and not necessary at all.

    Code:
    #include <stdio.h>
    #define Rows 5
    #define Cols 7
    
    int main(void) {
       int r, c, count, links, dirr; //dirr = direction
       int a[Rows][Cols] = {
       { 0,0,0,0,0,0,0 },
       { 0,1,1,1,0,1,0 },
       { 0,0,1,0,0,0,0 },
       { 0,0,0,0,1,1,0 },
       { 0,0,0,0,0,0,0 }, };
    
       count = links = 0;
       for(r=1;r<Rows-1;r++)  {
          putchar('\n');
          for(c= 1; c<Cols-1;c++)  {
             printf("%d ", a[r][c]);
             if(links == 0 && a[r][c])
                count++;
             if(a[r][c] == 1)  {
                for(dirr = 0, links = 0; dirr < 4; dirr++) {
                   if(a[r-1][c] == 1) {  //12 o'clock
                      links++; break; //you have a link, so quit the testing
                   }
    
                   //continue like the above, for the other 3 directions: 3, 6, and 9 o'clock
                }
                if(links == 0)
                   count++;
    
             }
          }
       }
       printf("\n This matrix has %d distinct groups ", count);
       printf("\n\n\t\t\t     press enter when ready ");
       r = getchar();
       return 0;
    }
    Last edited by Adak; 04-13-2009 at 04:37 PM.

  13. #13
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    This wasn't as easy as I thought it would be. The problem is with this configuration:

    Code:
    0 0 0 1
    0 1 1 1
    0 0 0 0
    The elements in red, will be counted as a new group, unless the program "walks" over the links, and finds the blue '1' in the row above them, knows that it's connected to it, and makes no increment of the group count.

    The earlier algorithm worked in 3 tested configurations, simply because the array was very small, which kept the configurations, relatively simple.

    This is my attempt to make this, more capable:

    Code:
    /* groups.c Finds distinct contiguous groups in a matrix. 
    Status: ok 
    */
    
    #include <stdio.h>
    
    #define Rows 6
    #define Cols 9
    
    int trails(int a[Rows][Cols], int r, int c);
    
    int main(void) {
       int r, c, group, links, ready, hit; 
    
       int a[Rows][Cols] = {
       { 0,0,0,0,0,0,0,0,0 },
       { 0,1,1,1,1,1,0,0,0 },
       { 0,0,1,0,0,0,0,1,0 },
       { 0,1,0,1,0,1,1,1,0 },     
       { 0,0,1,1,1,0,1,1,0 },     
       { 0,0,0,0,0,0,0,0,0 },
       };
    
       printf("\n\n");
       group = links = 0;
       ready = 1;
    
       for(r=1, hit= 0;r<Rows-1;r++)  {
          putchar('\n');
          for(c= 1; c<Cols-1;c++)  {
             printf("%d ", a[r][c]);
             if(a[r][c]) {
                if(a[r-1][c] == 1) {  //12 o'clock
                   links++; ready = 0; 
                }
                if(a[r][c+1] == 1) {  //3 o'clock
                   links++; 
                   hit = trails(a, r, c); 
                   if(hit) { 
                      ready = 0;  
                   }
                }
                if(a[r][c-1] == 1) {  //9 o'clock
                   links++;   
                }
             }
    
             if(!links) ready = 1;
             if(hit == 0 && ready == 1 && a[r][c]) {
                group++;
                ready = 0;
             }
             links = 0; hit = 0;
          }
       }
       printf("\n This matrix has 4 distinct groups. I found: %d groups ", group);
       printf("\n\n\t\t\t     press enter when ready ");
       r = getchar();
       return 0;
    }
    /* recursively calls itself to follow the trail of links upward and to the
       right, to see if it hits (is linked with), a previous sqr in an already 
       counted group.
    */
    int trails(int a[Rows][Cols], int r, int c) {
       //hit = 1 means you've hit a previous groups sqr 
       static hit = 0; 
       int link = 1;
    
       while(link > 0)  {
          if(a[r-1][c] == 1) {  //12 o'clock
             hit = 1; break;
          }
          else
             link = 0;
    
          if(a[r][c+1] == 1) {  //3 o'clock
             trails(a, r, c+1); 
          }
          else
             link = 0;
       }
       return hit;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Adding More Array Elements?
    By Vermillion in forum C++ Programming
    Replies: 2
    Last Post: 09-14-2008, 10:02 PM
  2. coping elements not in array
    By lord in forum C++ Programming
    Replies: 2
    Last Post: 08-04-2008, 07:53 PM
  3. way to check 3 elements of array and set 4th
    By Syneris in forum C++ Programming
    Replies: 3
    Last Post: 01-09-2006, 10:30 AM
  4. Class Template Trouble
    By pliang in forum C++ Programming
    Replies: 4
    Last Post: 04-21-2005, 04:15 AM
  5. A simple question about selecting elements in an array
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 08-30-2001, 10:37 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21