How about the following: 1. Think every cell on a board occupied by an "O" is a vertex in a non-directed graph. Add a special vertex called "OuterWorld". 2. Connect all neighboring vertices with edges, based on how you define "surrounded by X-es". E.g. in your picture, diagonals are not allowed. 3. Connect all vertices on the board's boundaries to the "OuterWorld" vertex.
Now, you should split your graph into connected subgraphs (use DFS or BFS - both will work). You will get at most one subgraph containing the "OuterWorld" vertex (which you don't touch) plus zero or more subgraphs of surrounded "O"-vertices (where you flip all vertices from "O" to "X". An alternative approach would be to represent "O"-regions using "Disjoint Sets" to and use "Find-And-Union" algorithm to solve it. Thanks! On Tuesday, June 11, 2013 3:05:30 AM UTC-4, Jai Shri Ram wrote: > > Given a 2D board containing 'X' and 'O', capture all regions surrounded > by 'X'. > > A region is captured by flipping all 'O's into 'X's in that surrounded > region . > > For example, > > X X X X > X O O X > X X O X > X O X X > > After running your function, the board should be: > > X X X X > X X X X > X X X X > X O X X > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
