CODEWITHSUNDEEP
javaalgorithmbreadth-first-search
nvio0
nvio0

Reputation: 9

Searching for the biggest area inside 2D matrix

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 can be connected either diagonally or adjacently.
  2. The area is considered coherent only if it is surrounded by the other type of pixel

Pixel is considered an object with 3 fields:

int x,y;
String type;
boolean visited;

The input file is something like this:

00000000

01100100

00111000

00010000

00000000

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

Upvotes: 0

Views: 76

Answers (1)

Deepak Tatyaji Ahire
Deepak Tatyaji Ahire

Reputation: 5311

BFS would be a better option to go with. More specifically, try a flood fill approach. By making a smart use of visited variable, make sure that you visit every vertex at-most once, hence keeping the time complexity as minimum as possible.

Upvotes: 1

Related Questions