/* Problem 4:  Jeff Horn's Robots
   This program finds and prints the shortest path a robot can take
   through a room with obstacles. */

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

typedef int BT[10][10];
typedef char GT[10][11];
typedef struct square {   /* a position vector within the grid */
         int x, y;
} square;

int main (int argc, char **argv);
void process (void);
void Bprocess (BT Board, int ct, square *ch, int chct);
void append (BT Board, int ct, square *ch, int *chct, int x, 
                    int y, char Dir);
void ReTourBoard (int pl,char *Tour);

int l, w;   /* length and width of the board */

GT Grid, Direction;  /* Grid is the room map, 
                        Direction stores path info*/

FILE *in, *out;

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

  int i;

 in = fopen ("prob4.in","r");
 out = fopen ("prob4.out","w");
 while (1) {
  fscanf (in,"%d %d ",&l,&w);   /* Read in length and width */
  if (l==0) break;
  for (i = 0; i < l; i++) fscanf (in,"%s",Grid[i]);
                /* Read in the grid */
  memset (Direction, 0, sizeof Direction); /* Initialize */
  process ();
 }
 fclose (in);
 fclose (out);
 return EXIT_SUCCESS;
}

/* process computes and prints out the shortest path.  It begins at the
   starting point and finds all reachable positions 1 move away and
   how to get there.
   From these it finds the squares two positions away, and how to get
   there, and so forth,
   until it has filled the room.  Then it prints the path needed to
   reach the destination square. */

void process (void) {

  char Tour[101] = {0};  /* path the robot takes */
  BT Board; /* contains the path length to every square */
  square ch[400]; /* the list of squares x moves from start */

 ch[0].x = ch[0].y = 0;   /* There is only one square 0 moves away */
 memset (Board,-1,sizeof Board);
 Board[0][0] = 0;
 Bprocess (Board,1,ch,1); /* Compute the paths of length > 0 */
 ReTourBoard (Board[l-1][w-1],Tour); /* Compute the path string */
 fprintf (out,"%s\n",Tour); /* Print the path string */
}

/* Bprocess accepts the board containing the squares already visited,
   and finds all squares on the board at least ct squares away
   from the starting point. ch is the list of squares ct-1 away from
   the starting point, and chct is the length of this list. */

void Bprocess (BT Board, int ct, square *ch, int chct) {

  int i, chctnew;
  square chnew[64];
    
 chctnew = i = 0;
 for (chctnew = i = 0; i < chct; i++) {
   /* Each square has four neighbors, add them to the list of
      squares ct moves from start. */
  append (Board,ct,chnew,&chctnew,ch[i].x,ch[i].y-1,'W');
  append (Board,ct,chnew,&chctnew,ch[i].x,ch[i].y+1,'E');
  append (Board,ct,chnew,&chctnew,ch[i].x-1,ch[i].y,'N');
  append (Board,ct,chnew,&chctnew,ch[i].x+1,ch[i].y,'S');
 }
/* If we haven't made it to the destination, find the ones at least ct+1
    moves away. */
 if (Board[l-1][w-1]==-1) Bprocess (Board,ct+1,chnew,chctnew);
}

/* append adds a square to a list of squares, but only if it's valid
   and has not been visited yet.  Board contains the visited squares,
   ct is the path length so far, ch is the list of squares
   chct is the length of that list.  x and y are the coordinates
   to be added.  Dir represents the direction being moved. */

void append (BT Board, int ct, square *ch, int *chct, int x, 
                    int y, char Dir) {

 if (x>=0 && x<l && y>=0 && y<w && Board[x][y] == -1 && 
             Grid[x][y] == '0') {
  Board[x][y] = ct;      /* Visit the square */
  Direction[x][y] = Dir; /* Indicate the direction moved. */
  ch[*chct].x = x;       /* Add the square to the list. */
  ch[*chct].y = y;
  (*chct)++;
 }
}

/* ReTourBoard starts from the destination point and builds the path
   string in reverse. pl is the path length, Tour is the path string.*/

void ReTourBoard (int pl,char *Tour) {

 l--; w--;  /* The coordinates of the destination square. */
 Tour[pl] = 0; pl--;
 for ( ;pl >=0; pl--) {
  Tour[pl] = Direction[l][w]; /* Pull out the direction */
  switch (Tour[pl]) {         /* Move accordingly. */
   case 'N': l++; break;
   case 'S': l--; break;
   case 'E': w--; break;
   case 'W': w++;
  }
 }
}