Populate Empty positions in a matrix to form Rectangles

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 the characters are unique.

Fill all empty cells with characters in such a way that if we draw the border around all cells of the same characters, we get a rectangle. One of the solutions for the above matrix is:

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

For example, the below placement of characters is wrong because A's and B's do not form a Rectangle

A A A
A B B
A B C

Solution:

There exists a greedy solution to this problem where we follow the following 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 following example:

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.