Given a matrix of ‘O’ and ‘X’, replace 'O' with 'X' if surrounded by 'X' - GeeksforGeeks

Given a matrix of 'O' and 'X', replace 'O' with 'X' if surrounded by 'X' - GeeksforGeeks
Given a matrix where every element is either 'O' or 'X', replace 'O' with 'X' if surrounded by 'X'. 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.

1) Traverse the given matrix and replace all ‘O’ with a special character ‘-‘.

2) Traverse four edges of given matrix and call floodFill(‘-‘, ‘O’) for every ‘-‘ on edges. The remaining ‘-‘ are the characters that indicate ‘O’s (in the original matrix) to be replaced by ‘X’.

3) Traverse the matrix and replace all ‘-‘s with ‘X’s.

// A recursive function to replace previous value 'prevV' at  '(x, y)'

// and all surrounding values of (x, y) with new value 'newV'.

void floodFillUtil(char mat[][N], int x, int y, char prevV, char newV)

{

    // Base cases

    if (x < 0 || x >= M || y < 0 || y >= N)

        return;

    if (mat[x][y] != prevV)

        return;

    // Replace the color at (x, y)

    mat[x][y] = newV;

    // Recur for north, east, south and west

    floodFillUtil(mat, x+1, y, prevV, newV);

    floodFillUtil(mat, x-1, y, prevV, newV);

    floodFillUtil(mat, x, y+1, prevV, newV);

    floodFillUtil(mat, x, y-1, prevV, newV);

}

// Returns size of maximum size subsquare matrix

// surrounded by 'X'

int replaceSurrounded(char mat[][N])

{

   // Step 1: Replace all 'O'  with '-'

   for (int i=0; i<M; i++)

      for (int j=0; j<N; j++)

          if (mat[i][j] == 'O')

             mat[i][j] = '-';

   // Call floodFill for all '-' lying on edges

   for (int i=0; i<M; i++)   // Left side

      if (mat[i][0] == '-')

        floodFillUtil(mat, i, 0, '-', 'O');

   for (int i=0; i<M; i++)  //  Right side

      if (mat[i][N-1] == '-')

        floodFillUtil(mat, i, N-1, '-', 'O');

   for (int i=0; i<N; i++)   // Top side

      if (mat[0][i] == '-')

        floodFillUtil(mat, 0, i, '-', 'O');

   for (int i=0; i<N; i++)  // Bottom side

      if (mat[M-1][i] == '-')

        floodFillUtil(mat, M-1, i, '-', 'O');

   // Step 3: Replace all '-' with 'X'

   for (int i=0; i<M; i++)

      for (int j=0; j<N; j++)

         if (mat[i][j] == '-')

             mat[i][j] = 'X';

}

Related:
Given a matrix of 'O' and 'X', find the largest subsquare surrounded by 'X'
Flood Fill
Read full article from Given a matrix of 'O' and 'X', replace 'O' with 'X' if surrounded by 'X' - GeeksforGeeks