Apr 232017
 

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 can be 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 has no alphabets. And copy the row above it (or below it) to it. Consider 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);
}

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(n2) time and constant extra memory.

pinkdiamonds.nl

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)