Algorithm - Colour surrounded by another colour in a matrix

Question

I recently faced this problem in an interview:

Given below matrix:

[[ R R R R R R],
 [ R B B B R R],
 [ B R R R B B],
 [ R B R R R R]]

Find out if any group of only R's or only B's surrounded by Opposite colour in the 4 directions: up, down, left, right corners.

ex: Answer for the above matrix -> Valid set of B's surrounded by R's in the second row.

[[ R R R R R R],
 [ R **B B B** R R],
 [ B R R R B B],
 [ R B R R R R]]

I tried doing a BFS for a specific colour in all directions but was unable to come up to solution. Can someone guide me to the solution.

Answer 1

To find the groups of B cells surrounded by R cells, think of the matrix as a graph whose vertices are all the B cells, with edges connecting adjacent B cells. Use BFS (or DFS) to find the connected components of this graph, but ignore the connected components that contain cells on the boundary. Each (non-boundary) connected component contains a set of B cells surrounded by R cells. Then, to find the groups of R cells surrounded by B cells, similarly compute the non-boundary connected components of the graph whose vertices are the R cells.

Since the number of vertices and edges of both graphs is O(mn) and the set of connected components of a graph can be found in time that is linear in the graph's size, the running time of this algorithm is O(mn).