# 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).
*/
```