/*
**    Sample solution to problem 5 from IOI6 day2
**
**    This version records the number of frames on top of each one.
**    It must allow for the fact that some don't directly cover a
**    particular frame.
*/
#include <fstream.h>

const int MAX_SIDE = 30;
const int MAX_FRAMES = 26;
const int FALSE = 0;
const int TRUE = !FALSE;

int h, w;

char sheet[MAX_SIDE][MAX_SIDE];

int num_frames = 0;

void get_input()
{
   char tmp;
   ifstream in("input.txt");

   in >> h >> w;

   for(int y = 0; y < h; y++)
      for(int x = 0; x < w; x++)
         {
         in >> tmp;

         if (tmp == '.')
            sheet[y][x] = MAX_FRAMES;
         else
            {
            tmp -= 'A';
            if (tmp + 1 > num_frames) num_frames = tmp + 1;
            sheet[y][x] = tmp;
            }
         }
}

int left[MAX_FRAMES], right[MAX_FRAMES], top[MAX_FRAMES], bottom[MAX_FRAMES];

// Find the left, right top, and bottom sides of the frame.
void find_sides()
{
   // Initialise each frame
   for (int n = 0 ; n < 26; n++)
      {
      left[n] = bottom[n] = MAX_SIDE;
      right[n] = top[n] = 0;
      }

   // Work your way through the sheet, updating values for left, right etc
   for(int y = 0 ; y < h; y++)
      for(int x = 0 ; x < w; x++)
         if (sheet[y][x] != MAX_FRAMES)
            {
            // Update sides of this frame
            if (left[sheet[y][x]] > x) left[sheet[y][x]] = x;
            if (right[sheet[y][x]] < x) right[sheet[y][x]] = x;
            if (bottom[sheet[y][x]] > y) bottom[sheet[y][x]] = y;
            if (top[sheet[y][x]] < y) top[sheet[y][x]] = y;
            }
}

int ontop[MAX_FRAMES][MAX_FRAMES];
int num_ontop[MAX_FRAMES];

/*
**    Count the number of frames on top of this one.
*/
void count_ontop(int frame)
{
   // Put left, right, bottom and top into local variables
   int LEFT = left[frame];
   int RIGHT = right[frame];
   int BOTTOM = bottom[frame];
   int TOP = top[frame];

   // Look on the top and bottom rows for a frame placed on this
   for(int x = LEFT; x <= RIGHT; x++)
      {
      // Bottom row
      if (sheet[BOTTOM][x] != frame)
         // Frame on top of us, have we counted it
         if(!ontop[sheet[BOTTOM][x]][frame])
            {
            num_ontop[frame]++;
            ontop[sheet[BOTTOM][x]][frame] = TRUE;
            }

      // Top row
      if (sheet[TOP][x] != frame)
         if(!ontop[sheet[TOP][x]][frame])
            {
            num_ontop[frame]++;
            ontop[sheet[TOP][x]][frame] = TRUE;
            }
      }

   // Look on the left and right columns (don't have to do the corners)
   for(int y = BOTTOM + 1; y < TOP; y++)
      {
      // Left side
      if (sheet[y][LEFT] != frame)
         if(!ontop[sheet[y][LEFT]][frame])
            {
            num_ontop[frame]++;
            ontop[sheet[y][LEFT]][frame] = TRUE;
            }

      // Right side
      if (sheet[y][RIGHT] != frame)
         if(!ontop[sheet[y][RIGHT]][frame])
            {
            num_ontop[frame]++;
            ontop[sheet[y][RIGHT]][frame] = TRUE;
            }
      }
}

// This array contains the frames in order.
int ordered[MAX_FRAMES];

update_ontop()
{
   for(int uncovered = 0; uncovered < num_frames - 1; uncovered++)
      for(int current = 0; current < num_frames; current++)
         if (num_ontop[current] == uncovered)
            {
            // This is the next uncovered frame
            // and ensure that it is on top of all the others
            for(int frame = 0; frame < num_frames; frame++)
               if (!ontop[current][frame] && !ontop[frame][current]
                  &&current != frame)
                  {
                  num_ontop[frame]++;
                  ontop[current][frame] = TRUE;
                  }

            break;   // Found the current on top, search for next
            }
}

void print_ordered()
{
   for(int frame = 0; frame < num_frames; frame++)
      cout << (char) (ordered[frame] + 'A');
   cout << endl;
}

void main()
{
   get_input();

   find_sides();  // Find the sides of each frame

   // First pass through to find number of frames ontop of each other
   for(int frame = 0; frame < num_frames; frame++)
      count_ontop(frame);

   // This however won't give the correct number of frames on top of any
   // other unless a frame covers all those beneath it.
   // Here we find the next uncovered frame, and ensure that it covers
   // all frames below it.
   update_ontop();

   // Now we now how many on top of each frame, stck in output array
   for(frame = 0; frame < num_frames; frame++)
      ordered[num_ontop[frame]] = frame;

   print_ordered();  // And print them
}
/*
**    Most work is done in the three for loops where the num_ontop
**    array is updated. This could be reduced by putting the output
**    from the first pass into a priority queue, and updating the
**    elements if a frame is found on top of another.
*/
