CODEWITHSUNDEEP
calgorithmgraph-algorithm
barp
barp

Reputation: 6929

Graph algorithm in C by reading grids into array

I need to read some objects from console.It is a bit like the battleship game written in C. Think of it I have a platform of 6x6 array.I am taking the user input from the user and the char 'X' means it is a shaded area in the two dimensional array.I am assigning the chars for the 36 place.The example of the array after user has given the inputs is;

0,0                       0,6      

  X              XXX
 X                X  
   XX             X 
     X




6,0                       6,6

Sorry the output is not too clear.It is the output of the X chars that user had entered.The 'x' chars in the two groups are unioned and so, there are 2 objects in the graph.I need to count the number of the groups.The direction of the X chars is not able to be symetric, all the thing is there may be group of x chars that are unioned and i want to count the groups

Upvotes: 0

Views: 263

Answers (1)

amit
amit

Reputation: 178421

Model the problem as the graph (as you already understood): G=(V,E), where V is your grid (or only the x's to be more exact), and E = { (u,v) | there is X in both u and v }

During parsing, save all your coordinates in an container, and map each to a boolean value indicating if it was visited or not.

Now, repeat while there are still non visited x's:
Run a graph discovery algorithm (BFS is an example) from this (not visited) x, and mark all visited x's encountered during the run of the discovery algorithm

The number of iterations (number of times BFS was invoked) is the number of groups.

Upvotes: 1

Related Questions