Search code examples
algorithmmatrixpathpath-finding

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.

Solution

  • 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