/* Problem 1--Changing Maze
   This can actually be solved with breadth-first search like a normal
   maze; very little needs to be adjusted. */

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

#define MAX 20

typedef struct square {
 int t, r, c;  /* holds the row, column, and time step */
} square;

int main (int argc, char **argv);
int process (void);
int Bprocess (int ct, square *ch, int chct);
int append (int mv, square *ch, int *chct, int r, int c, int t);

FILE *in, *out;
char MZ[10][MAX+2][MAX+2]; /* put row of boundaries all around maze */
int Board[10][MAX+2][MAX+2]; /* Stores how long it takes to make it
                                to that square. */
int col, row, ct;

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

  char A[MAX+2];
  int i, j, pl, cs=0;

 in = fopen ("prob1.in","r");
 out = fopen ("prob1.out","w");
 while (fscanf (in,"%d %d %d",&row,&col,&ct),row>0) {
  memset (MZ,'1',sizeof MZ); /* fill maze up with boundaries */
  memset (Board,-1,sizeof Board);
  for (i=0; i < ct; i++)  /* read in the patterns */
   for (j=0; j < row; j++) {
    fscanf (in,"%s",A);
    memcpy (&MZ[i][j+1][1],A,col);
   }
  if ((pl=process ()) > -1)
   fprintf (out,"Case %d:  Luke and Leia can escape in %d steps.\n",
            ++cs,pl);
  else
   fprintf (out,"Case %d:  Luke and Leia cannot escape.\n",++cs);
 }
 fclose (in);
 fclose (out);
 return EXIT_SUCCESS;
}

/* Process returns the minimum number of steps needed to make it through
   or -1 if the maze cannot be solved. */

int process (void) {

  square ch[400]; /* the list of squares x moves from start */

 ch[0].t = 0; ch[0].r = ch[0].c = 1; /* It takes zero moves to make it*/
 Board[0][1][1] = 0;                 /* to the beginning. */
 return Bprocess (1,ch,1); /* Compute the paths of length > 0 */
}

/* Bprocess 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.  It
   returns the minimum number of time steps necessary to complete
   the maze or -1 if it can't be done. */

int Bprocess (int mv, square *ch, int chct) {

  int i, chctnew;
  square chnew[400];

 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, as well as the current square,
      but at the next time step.  If, at any time, we reach the end,
      we return the number of steps it took to get there. */
  if (append (mv,chnew,&chctnew,ch[i].r,ch[i].c,(ch[i].t+1)%ct))
   return Board[(ch[i].t+1)%ct][ch[i].r][ch[i].c];
  if (append (mv,chnew,&chctnew,ch[i].r,ch[i].c-1,(ch[i].t+1)%ct))
   return Board[(ch[i].t+1)%ct][ch[i].r][ch[i].c-1];
  if (append (mv,chnew,&chctnew,ch[i].r,ch[i].c+1,(ch[i].t+1)%ct))
   return Board[(ch[i].t+1)%ct][ch[i].r][ch[i].c+1];
  if (append (mv,chnew,&chctnew,ch[i].r-1,ch[i].c,(ch[i].t+1)%ct))
   return Board[(ch[i].t+1)%ct][ch[i].r-1][ch[i].c];
  if (append (mv,chnew,&chctnew,ch[i].r+1,ch[i].c,(ch[i].t+1)%ct))
   return Board[(ch[i].t+1)%ct][ch[i].r+1][ch[i].c];
 }
  /* If we haven't made it to the goal and there are no more squares
     to check, return -1.  Otherwise, check the new squares. */
  if (chctnew==0) return -1;
  return Bprocess (mv+1,chnew,chctnew);
}

/* append adds a square to a list of squares, but only if it's valid
   and has not been visited yet.  ct is the path length so far; ch is
   the list of squares; chct is the length of that list.  r, c, and t
   are the coordinates to be added. */

int append (int mv, square *ch, int *chct, int r, int c, int t) {

 /* If this is an invalid or already visited square, we're not done. */
 if (MZ[t][r][c] != '0' || Board[t][r][c]!=-1) return 0;
 Board[t][r][c] = mv;      /* Visit the square */
 ch[*chct].t = t;
 ch[*chct].r = r;       /* Add the square to the list. */
 ch[*chct].c = c;
 (*chct)++;
 return r==row && c==col; /* If we reached the end, we're done! */
}