#include <stdio.h>
#include <string.h>

char puzzle[64][64];
int rows, cols;
char words[1024][64];
int numWords;

void getWords()
{
    int i, j, k;
    int letter;

    // Initialize the word array and counter
    memset(words, 0, sizeof(words));
    numWords = 0;

    // Scan the puzzle rows from left to right, top to bottom
    for (i = 1; i <= rows; i++)
    {
        for (j = 1; j <= cols; j++)
        {
            // See if there's a letter here
            if (puzzle[i][j] != 0)
            {
                // First check for a down word
                if ((puzzle[i+1][j] != 0) && (puzzle[i-1][j] == 0))
                {
                    // We've got a word, initialize the first two letters
                    // (which we just discovered)
                    words[numWords][0] = puzzle[i][j];
                    words[numWords][1] = puzzle[i+1][j];
 
                    // Now, finish the word
                    k = i+2;
                    letter = 2;
                    while ((puzzle[k][j] != 0) && (k <= rows))
                    {
                        words[numWords][letter] = puzzle[k][j];
                        k++;
                        letter++;
                    }

                    // Increment the word counter
                    numWords++;
                }

                // Now, check for an across word
                if ((puzzle[i][j+1] != 0) && (puzzle[i][j-1] == 0))
                {
                    // We've got a word, initialize the first two letters
                    // (which we just discovered)
                    words[numWords][0] = puzzle[i][j];
                    words[numWords][1] = puzzle[i][j+1];

                    // Now, finish the word
                    k = j+2;
                    letter = 2;
                    while ((puzzle[i][k] != 0) && (k <= cols))
                    {
                        words[numWords][letter] = puzzle[i][k];
                        k++;
                        letter++;
                    }

                    // Increment the word counter
                    numWords++;
                }
            }
        }
    }
}

void sortWords()
{
    int i, numPass;
    char temp[64];
    bool exch;

    // Initialize
    numPass = numWords - 1;
    exch = true;

    // Bubble sort
    while (exch)
    {
        // No exchange made yet on this pass
        exch = false;

        // Swap the words that are out of order
        for (i = 0; i < numPass; i++)
        {
            // Compare and swap the next pair of words, if necessary
            if (strcmp(words[i], words[i+1]) > 0)
            {
                strcpy(temp, words[i]);
                strcpy(words[i], words[i+1]);
                strcpy(words[i+1], temp);
                exch = true;
            }
        }

        // Decrement the length of the pass by 1
        numPass--;
    }
}

int main(void)
{
    FILE *fp, *fpOut;
    char line[100], *nl;
    int puzzleCount;
    int i, j;

    // Open the input and output files
    fp = fopen("puzzle.dat", "r");
    fpOut = fopen("puzzle.out", "w");

    // Initialize the puzzle count
    puzzleCount = 0;

    // Read in the number of rows and columns
    fgets(line, sizeof(line), fp);
    nl = strchr(line, '\n');
    if (nl != NULL)
        *nl = 0;
    sscanf(line, "%d %d", &rows, &cols);

    // Repeat as long as we have a valid puzzle size
    while (rows > 0)
    {
        // Clear the puzzle array and increment the puzzle count
        memset(puzzle, 0, sizeof(puzzle));
        puzzleCount++;

        // Read in the puzzle.  We'll pad it with a blank row on the top
        // and a blank column on the left
        for (i = 1; i <= rows; i++)
        {
            // Read in the next line of the puzzle
            fgets(line, sizeof(line), fp);
            nl = strchr(line, '\n');
            if (nl != NULL)
                *nl = 0;

            for (j = 1; j <= cols; j++)
            {
                if (line[j-1] != '_')
                    puzzle[i][j] = line[j-1];
            }
        }

        // Now, scan the puzzle for words...
        getWords();

        // ... sort the words into alphabetical order ...
        sortWords();

        // ... and print them out
        fprintf(fpOut, "Puzzle #%d\n", puzzleCount);
        for (i = 0; i < numWords; i++)
            fprintf(fpOut, "%s\n", words[i]);

        // Leave a blank line
        fprintf(fpOut, "\n");

        // Read in the number of rows and columns for the next puzzle
        fgets(line, sizeof(line), fp); 
        nl = strchr(line, '\n'); 
        if (nl != NULL)
            *nl = 0;
        sscanf(line, "%d %d", &rows, &cols);
    }

    // Close our files
    fclose(fp);
    fclose(fpOut);

    return 0;
}