Given a 2-D matrix M where every element is either ‘O’ or ‘X’, write a program to replace ‘O’ with ‘X’ if surrounded by ‘X’.

Problem Note

  • A ‘O’ or a set of ‘O’ is considered to be by surrounded by ‘X’ if there are ‘X’ at locations just below, just above, just left and just right of it.
  • Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'.
  • Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'.
  • Two cells are connected if they are adjacent cells connected horizontally or vertically.

Example 1

Input: M[][] = [ 
                 ['X', 'O', 'X', 'X', 'X', 'X'],
                 ['X', 'O', 'X', 'X', 'O', 'X'],
                 ['X', 'X', 'X', 'O', 'O', 'X'],
                 ['O', 'X', 'X', 'X', 'X', 'X'],
                 ['X', 'X', 'X', 'O', 'X', 'O'],
                 ['O', 'O', 'X', 'O', 'O', 'O'],
               ]
Output: M[][] = [ 
                  ['X', 'O', 'X', 'X', 'X', 'X'],
                  ['X', 'O', 'X', 'X', 'X', 'X'],
                  ['X', 'X', 'X', 'X', 'X', 'X'],
                  ['O', 'X', 'X', 'X', 'X', 'X'],
                  ['X', 'X', 'X', 'O', 'X', 'O'],
                  ['O', 'O', 'X', 'O', 'O', 'O'],
                ]

Example 2

Input: M[][] = [ 
                 ['X', 'X', 'X', 'X']
                 ['X', 'O', 'X', 'X']
                 ['X', 'O', 'O', 'X']
                 ['X', 'O', 'X', 'X']
                 ['X', 'X', 'O', 'O']
               ]
Output: M[][] = [ 
                  ['X', 'X', 'X', 'X']
                  ['X', 'X', 'X', 'X']
                  ['X', 'X', 'X', 'X']
                  ['X', 'X', 'X', 'X']
                  ['X', 'X', 'O', 'O']
                ]