1
$\begingroup$

so I've a algorytmical problem where i need to find the biggest area of a certain type of pixels inside a 2D matrix with following conditions:

  1. Each pixel needs to be connected either diagonally or adjacently.
  2. The area is considered coherent only if it is surrounded by the other type of pixel( x-es on the edge are not)

Pixel is considered an object with 3 fields:

int x,y;          //Cordinates of a pixel
String type;      //Type of a pixel
boolean visited;  //Was the pixel visited

The input file is something like this:

oooooooooo 
oXXooXXXoo
oooXoooooo
xooooXXXXo
xxooXooooo
xxxooooooo

The output in this example should be an int of value 5.

Is someone able to tell me if BFS algorithm is a viable solution or should I try a different approach?

$\endgroup$
  • $\begingroup$ I fail to see where the number 5 as an output is coming from. Please mark it in another diagram or/and explain more. $\endgroup$ – Apiwat Chantawibul Oct 22 at 0:30
  • $\begingroup$ @ApiwatChantawibul The Xs in the lower right are all connected, and all together are a group of five, diagonals count. $\endgroup$ – KrystosTheOverlord Oct 22 at 0:36
  • $\begingroup$ A combination of a BFS and a flood fill would prob be best for this application. If you are really tight on time, you could even use something like a hashmap to store specific characters and their indices in the 2d array, and once they have been traversed, remove them from the Hashmap, this will result in an O(1) time complexity for lookup, and make your overall time complexity more like O(n) if I'm not mistaken $\endgroup$ – KrystosTheOverlord Oct 22 at 0:42
  • $\begingroup$ No, lower left group is 6 if I'm not crazy. $\endgroup$ – Apiwat Chantawibul Oct 22 at 0:42
  • $\begingroup$ @ApiwatChantawibul I just noticed that too, I think the creator of this question was asking about a particular group, the capital Xs, or it is a typo. $\endgroup$ – KrystosTheOverlord Oct 22 at 0:54
0
$\begingroup$

A BFS combined with floodfill should be enough.

Basically, you do the following:

  1. Iterate until you find the first X
  2. Run a BFS on it and change all pixels to visisted = True. Also keep track if you happen to reach the boundary or fulfill any other criterion s.t. it is disqualified
  3. If it is not disqualified, save its size as the current max-size
  4. Iterate further until you find the next unvisited pixel and redo steps 2-4. Keep track of the largest size found.
  5. If you need the original array, change back the visisted state of each pixel in a final iteration.

Overall runtime: Linear, because you change each element at most twice (once to visisted and once back), and also consider only a constant number of neighbors for each element (8).

$\endgroup$
  • $\begingroup$ Awesome m8, thanks for the response. I'll try it. $\endgroup$ – nvio0 Oct 23 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.