Rectangles in a matrix

Given a character matrix in which some of the cells have alphabets written on them while other cells are empty (empty cells contains character ‘-‘ in them). For example consider the below matrix:

A - -
- B -
- - C

All characters are unique. Set character on all empty cells in such a way that if we draw border around all cells of same characters, we get a rectangle. One of the solution for the above matrix is:

There are multiple solutions possible for a given input matrix. Write code to print one of the possible solutions.
Solution:

There exist a greedy solution to this problem where we follow below logic for each row:

Populate leading empty cells with the first character found.

For each alphabet in the row,

    populate all other cells following it with the same character
till we reach the end or encounter another character.

After doing it We need to look for rows that have no alphabets. And copy the row above it (or below it) to it. Consider the

below examples:

Input Matrix
    - - - - -
    - B - C -
    A - X - -

Extend characters of each Row
    - - - - -
    B B B C C
    A A X X X

Copy neighbouring row to empty rows
    B B B C C
    B B B C C
    A A X X X

Below is the code for the same:

#define M 4
#define N 5
#define EMPTY_CHAR '-'
// Copy the contents of row 's' to row 'd'
void copyRow(char arr[M][N], int d, int s)
{
   for(int i=0; i<N; i++)
      arr[d][i] = arr[s][i];
}
void printArray(char arr[M][N])
{
   cout<<"Matrix : \n";
   for(int i=0; i<M; i++)
   {
      for(int j=0; j<N; j++)
         cout<<arr[i][j]<<" ";
      cout<<endl;
   }
}
void populateMatrix(char arr[M][N])
{
   // extend characters in each row
   for(int i=0; i<M; i++)
   {
      char prevChar = EMPTY_CHAR;
      for(int j=0; j<N; j++)
      {
         if(arr[i][j] == EMPTY_CHAR)
         {
            if(prevChar != EMPTY_CHAR)
               arr[i][j] = prevChar;
         }
         else
         {
            // FIRST CHACTER ENCOUNTERED
            if(prevChar == EMPTY_CHAR)
            {
               // SET ALL THE PREV POS IN THIS ROW TO THIS CHAR
               for(int k=j-1; k>=0; k--)
                  arr[i][k] = arr[i][j];
            }
            prevChar = arr[i][j];
         }
      }
   }
   // Fix the empty rows.
   for(int i=0; i<M; i++)
   {
      // Checking first cell in the row is sufficient to see
      // If the entire row is empty or not.
      if(arr[i][0] == EMPTY_CHAR)
      {
         if(i==0)
         {
            // find the first non-empty row and then copy it here.
            int j=1;
            for(; j<M; j++)
               if(arr[j][0] != EMPTY_CHAR)
                  break;
            copyRow(arr, i, j);
         }
         else
            copyRow(arr, i, i-1);
      }
   }
}
int main()
{
   char arr[M][N] = {
      { '-', 'B', '-', 'C', '-'},
      { '-', '-', '-', '-', '-'},
      { '-', '-', 'A', '-', 'X'},
      { '-', '-', '-', '-', '-'}};
   printArray(arr);
   populateMatrix(arr);
   printArray(arr);
}

The output of this will be:

Matrix :
  - B - C -
  - - - - -
  - - A - X
  - - - - -
Matrix :
  B B B C C
  B B B C C
  A A A A X
  A A A A X

The code will take O(n²) time and constant extra memory.