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