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

Join Date
Apr 2013
Posts
39
Rep Power
6

#### 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. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Apr 2013
Posts
39
Rep Power
6
Does anyone know?
3. 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?
4. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Apr 2013
Posts
39
Rep Power
6
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.
5. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Apr 2013
Posts
39
Rep Power
6
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?
6. Sounds right, but I'm not sure why you need a recursive algorithm. Dijkstra's algorithm would work fine.