CODEWITHSUNDEEP
algorithmmatrixpathpath-finding
Bence Sebők
Bence Sebők

Reputation: 23

Finding path and inner fields in 2D matrix

I need to find closed path in a 2D matrix. Each element can have 3 colors, for simplification let's say: white, red, blue. I attach an image for demonstration here

So the main points of my problem are:

  1. Detect whether red fields are forming a closed path, ignoring white fields.
  2. If a closed path is detected (just like red line on the image), determine the inner field indexes (pink fields on the image)

I was thinking on using a path-finding algorithm, but they can't give me those pink fields.

What algorithm should I implement here?

Thank you.

Upvotes: 2

Views: 218

Answers (1)

neiht
neiht

Reputation: 313

If your final purpose is to find those pink fields then you can go through the matrix first to find an initial pink field, then use FloodFill(with BFS or DFS) to expand from that pink field to an area of pink fields with the red fields as boundary (i.e. base case in the BFS or DFS).

Those red fields boundary of your pink fields areas will be your closed path if the pink fields area does not expand all the way to the border of the matrix

Upvotes: 2

Related Questions