#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2013
    Posts
    23
    Rep Power
    0

    Checking adjacent elements in a 2d array c++


    I am trying to find out if the elements in my array are connecting:
    Example i have a 3 x 3 array and these are the elements:
    The array could be 15 x 15 or even 40 x 40
    ignore anything but a p

    so if this is the array

    s s s
    p p s
    p s p

    I would have 2 connected sections because diagonal does not count. So 1, 0 and 1, 1 and 2, 0 would be connected and 2,2 would be the 2nd section.

    I have written some code for it but keep coming up empty handed any help would be greatly appreciated.

    What i have tried is using a double for loop to loop through the array and then check the rt and up element in the array to see if they are a p as well, if they are then mark them but my only problem here is that if there is more than one element down or right it does not get saved into that 'patch', so do i have to check up and left to see if it is marked and if it is then add that to the patch number that is there or is there a simpler way to do this?
  2. #2
  3. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2013
    Posts
    23
    Rep Power
    0
    Does anyone know?
  4. #3
  5. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,895
    Rep Power
    481
    I'd use a graph search algorithm.
    You want the number of islands?
    Given two cells you want to know if they're connected?
    You want the number of islands and the cells in each?
    [code]Code tags[/code] are essential for python code and Makefiles!
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2013
    Posts
    23
    Rep Power
    0
    Yes i need the number of islands and the cells in each island. Thanks a lot. I am researching that algorithm now. Yes to all of your questions. I am just stuck on the part to find the islands, I am sure it would be a recursive function but the function itself is eluding me. I appreciate your time.
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2013
    Posts
    23
    Rep Power
    0
    Please correct me if i am wrong but what i am needing to do in words are as follows, this is what i am thinking not implementing as of yet because i have not done a thorough enough design dosument to continue:

    will be a method
    I need a check to make sure:
    1. that it is in bounds
    2. that it is a p
    3. that it has not been marked yet
    4. mark it
    5. increment the element counter for that island

    Then i need a method with which ever algorithm i want to use, dfs is most familiar to me, not sure if this is the best yet or not

    Then i need another method:
    1. an array to mark the visited elements
    2. make sure that all elements are initially unvisted
    3. then traverse through all the elements of the array
    4. check to make sure that an element is not visited yet,
    and if that is correct there is a new island
    5. increment the counter for the island

    Does this sound close to the necessary items needed for the methods, have i forgotten anything?
  10. #6
  11. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,895
    Rep Power
    481
    Sounds right, but I'm not sure why you need a recursive algorithm. Dijkstra's algorithm would work fine.
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo