Denis' Solution 2A: Where's Waldorf?

This is the personal work of Denis Dmitriev; it is not an officially verified or endorsed solution.

Denis writes: The problem was obviously designed just to test some basic abilities to write programs using given specification (so-called `technical problem'). Therefore the solution is nothing else but a translation from English to C++. -DD


C++ Source Code

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

/* all the possible directions in which the word can go */
int dir_x[8]={1,1,0,-1,-1,-1,0,1};
int dir_y[8]={0,-1,-1,-1,0,1,1,1};

#define HORZ_SIZE       51

int h,w;

/* checks if the word matches the sequence of letters of the grid */
bool check_word(char letters[][HORZ_SIZE],int y,int x,int dy,int dx,char
*word)
{
    for(;x>=0&&x<w&&y>=0&&y<h&&*word;x+=dx,y+=dy)
        if(*word++!=letters[y][x])
            return false;
    return !*word;
}

void main(void)
{
    FILE *fp=fopen("wal.in","r");
    FILE *fo=fopen("wal.out","w");

    char buf[256];
    fgets(buf,256,fp);
    int ntests=atoi(buf);

    for(;ntests--;)
    {
        fgets(buf,256,fp);

        int i,j;
        sscanf(buf,"%d %d",&h,&w);

        char letters[51][HORZ_SIZE];
        for(i=0;i<h;i++)
        {
            /* read the grid (to simplify things in the future
             * everything is converted to the lower case. we are
             * allowed to do so because the case should be
             * ignored)
             */
            fgets(buf,256,fp);
            for(j=0;j<w;j++)
                letters[i][j]=tolower(buf[j]);
        }

        fgets(buf,256,fp);
        int nwords=atoi(buf);

        for(;nwords--;)
        {
            /* read the word and convert it to lower case */
            fgets(buf,256,fp);
            sscanf(buf,"%s",buf);
            strlwr(buf);

            /* check for the presence of the word in the grid */
            for(i=0;i<h;i++)
                for(j=0;j<w;j++)
                    for(int k=0;k<8;k++)
                        if(check_word(letters,i,j,dir_y[k],dir_x[k],buf))
                            goto end;

end:            /* report the answer (there should be one [see
note]) */
            fprintf(fo,"%d %d\n",i+1,j+1);
        }

        /* separate test cases */
        fprintf(fo,"\n");
    }

    fclose(fo);
    fclose(fp);
}

/** Note:
 * There exists an inconsistency in the sample input/output for this
 * problem.
 * In the specification it is said that `All words can be found at least
 * once
 * in the grid', but it is easy to see that in the given sample input the
 * second word in the first test case (`ab') is not present in the grid.
 * Since
 * it contradicts the problem statement, the result produced by the correct
 * program run on it cannot be predicted. This solution prints the coords
 * that
 * are outside of the boundaries by one (`3 3' in this particular case).
 */