2D Array consecutive elements algorithm

Question

I have had a task given to me which requires me to ask user for a size of 2D Array, we need to create a 2D array with the specified size, so if user opted for 8 as the size, we make an 8x8 array and we randomly fill it with either 'X' or 'O'.

Now the main task is to find number of groups in that 2D array.

4 or more 'X' which are connected (horizontally OR vertically NOT diagonally) are what makes a group.

For example, there are 3 groups on the following photo:

My question is if there is (there probably is) an algorithm that deals with similar problems, so please do provide reading material if you have any.

a) isn't there one more group in the south-west corner? b) isn't that to easy, to ask for an algorithm? — user unknown
– user unknown, Commented Feb 17, 2018 at 22:43
@userunknown No there isn't, the requirement for 'X'-es to form a group is to have 4 of those linked horizontally or vertically, there are only 3 there. — whatamidoingwithmylife
– whatamidoingwithmylife, Commented Feb 17, 2018 at 23:10
Ah, the off-by-one-error hit again. :) Well, I overlooked the minimum size of island requierement. But if you don't have fun, working such a thing out on your own, providing at least the base of a maybe suboptimal solution - why do want to program? Show us your efforts. — user unknown
– user unknown, Commented Feb 17, 2018 at 23:16
@userunknown I already solved this as it was required for an exercise I was given on the course I'm attending, the problem is it was too complicated (too many loops and condition checks) and I simply knew that there was an algorithm of some sort for problems of this kind, hence the thread. I have some basic knowledge of algorithms, but I have yet to read a whole book on the subject, even though I have few of them on my Google Drive for when I get some free time. — whatamidoingwithmylife
– whatamidoingwithmylife, Commented Feb 17, 2018 at 23:22

DAle · Accepted Answer · 2018-02-18 00:00:49Z

1

Your task is a particular case of the finding the number of connected components in a graph. It can be solved with a breadth-first search or a depth-first search algorithms.

Pseudocode of dfs version:

result = 0
for every non-visited cell with 'X' value
    if groupSize(cell.x, cell.y) > 3
        result += 1
return result  

groupSize(x, y)
    size = 0 
    if cell(x, y) is inside array, non-visited and has 'X' value
        mark cell(x, y) as visited  
        size = 1
        size += groupSize(x + 1, y)
        size += groupSize(x - 1, y)
        size += groupSize(x, y + 1)
        size += groupSize(x, y - 1)
    return size

edited Feb 18, 2018 at 0:00

answered Feb 17, 2018 at 22:36

DAle

9,1922 gold badges28 silver badges48 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

whatamidoingwithmylife Over a year ago

Just read your links and it does seem to be what I was asking for.

Collectives™ on Stack Overflow

2D Array consecutive elements algorithm

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related