/* Problem 1:  Mark Terwilliger's Word Search
   This program takes a grid of letters and searches for words within
   that grid. */

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

typedef char GT[10][11];

int main (int argc, char **argv);
int Search (GT Grid, char *Word, int n, int *r, int *c);
void Reverse (GT A, GT B, int n);
void Transpose (GT A, GT B, int n);
void SearchAll (GT Grid, char *Word, int n, GT R, GT T, GT RT);

FILE *in, *out;

int main (int argc, char **argv) {

  GT Grid, R, T, RT; /* Word grid, Reverse grid, Transpose grid, both */
  int n, i, wct; /* size of grid, loop counter, number of words */
  char Word[9];  /* a read-in word */

 in = fopen ("prob1.in","r");
 out = fopen ("prob1.out","w");
 while (1) {
  fscanf (in,"%d ",&n);  /* get grid size */
  if (n==0) break;
  memset (Grid,0,sizeof Grid);  /* initialize grid */
  memset (R,0,sizeof R);  /* initialize grid */
  memset (T,0,sizeof T);  /* initialize grid */
  memset (RT,0,sizeof RT);  /* initialize grid */
  for (i=0; i < n; i++) fscanf (in,"%s",Grid[i]);
  Reverse (Grid,R,n);
  Transpose (Grid,T,n);
  Reverse (T,RT,n);
  fscanf (in,"%d ",&wct);
  for (i=0; i < wct; i++) {  /* read in each word */
   fscanf (in,"%s ",Word);       
   SearchAll (Grid,Word,n,R,T,RT);  /* search for it */
  } 
  fprintf (out,"\n");
 }
 fclose (in);
 fclose (out);
 return EXIT_SUCCESS;
}

/* Search accepts a grid, a word, and a grid size, and searches the
   grid for that word horizontally, returning the row and column
   number when found */

int Search (GT Grid, char *Word, int n, int *r, int *c) {

  int i;
  char *p;

 for (i=0; i < n; i++) /* Search each row */
  if (NULL != (p = strstr (Grid[i],Word))) { 
   *r = i; *c = p-Grid[i]; return 1;
  }
 return 0;
}

/* Reverse computes the mirror image of a grid */

void Reverse (GT A, GT B, int n) {

  int i, j;

 for (i = 0; i < n; i++)
  for (j = 0; j < n; j++)
   B[i][n-j-1] = A[i][j];
}

/* Transpose computes the transpose of a grid. */

void Transpose (GT A, GT B, int n) {

  int i, j;

 for (i = 0; i < n; i++)
  for (j = 0; j < n; j++)
   B[j][i] = A[i][j];
}

/* SearchAll searches the grid in all directions for the word. */

void SearchAll (GT Grid, char *Word, int n, GT R, GT T, GT RT) {

  int r, c;

 if (Search (Grid,Word,n,&r,&c)) {  /* Searching forward */
  fprintf (out,"%s %d %d R\n",Word,c+1,r+1);
  return;
 }
 if (Search (R,Word,n,&r,&c)) { /* Searching backward */
  fprintf (out,"%s %d %d L\n",Word,n-c,r+1);
  return;
 }
 if (Search (T,Word,n,&r,&c)) { /* Searching up */
  fprintf (out,"%s %d %d D\n",Word,r+1,c+1);
  return;
 }
 if (Search (RT,Word,n,&r,&c)) {/* Searching down */
  fprintf (out,"%s %d %d U\n",Word,r+1,n-c);
  return;
 }
 fprintf (out,"%s WAS NOT FOUND\n",Word);
}