/* Problem 3--Ro and Bot Meet
   This wasn't too hard per se, just a bit tedious.  All you need do
   is emulate the functioning of the robots.  The rules about no loops
   allowed and the order in which Ro and Bot check for open doors boils
   down to this:  Ro hugs the left-hand wall; Bot hugs the right-hand
   wall.  This is all that needs to be emulated. */

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

int main (int argc, char **argv);
void Initialize (void);
void Process (void);
void Advance (int dir,int *r, int *c, int *dr, int *dc);
void Right (int dir,int *dr, int *dc);
void Left (int dir,int *dr, int *dc);
int LeftSide (int dir,int dr,int dc);
int RightSide (int dir,int dr, int dc);
int DirectSide (int dr, int dc);

FILE *in, *out;
int r, c, M[20][20], mct=0;

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

 in = fopen ("prob3.in","r");
 out = fopen ("prob3.out","w");
 while (1) {
  fscanf (in,"%d %d",&r,&c);
  if (r==0 && c==0) break;
  Initialize ();
  Process ();
 }
 fclose (in);
 fclose (out);
 return EXIT_SUCCESS;
}

/* Initialize reads in the maze information, converting the hex numbers
   into integers. */
void Initialize (void) {

  int i, j;
  char ch;

 mct++;
 for (i = 0; i < r; i++)
  for (j = 0; j < c; j++) {
   fscanf (in," %c",&ch);  /*Read the char skipping prev whitespace */
   if (ch >= '0' && ch <= '9') M[i][j] = ch-'0';
   else M[i][j] = ch-'A'+10; /*converting letters to numbers*/
  }
}

/* Process advances Ro and Bot through the maze until they meet or
   exit. */
void Process (void) {

  int r1 = 1, c1 = 1, r2 = r, c2 = c, /* The positions of the robots*/
      dr1 = 0, dc1 = 1, dr2 = 0, dc2 = -1; /* Their orientations */

 while( (r1!=r || c1!=c)  &&  (r1!=r2 || c1!=c2) ) {
  Advance (1,&r1,&c1,&dr1,&dc1); /*Advancing */
  Advance (0,&r2,&c2,&dr2,&dc2);
 }
 if (r1==r && c1==c)  /* Exit */
  fprintf (out,"Maze %d: The robots do not meet.\n\n",mct);
 else  /* Met */
  fprintf (out,"Maze %d: The robots meet in row %d, column %d.\n\n",mct,
               r1,c1);
}

/* Advance moves one robot one position.  If dir is 1, it will hug the
   left-hand wall.  If dir is 0, it will hug the right-hand wall. */
void Advance (int dir,int *r, int *c, int *dr, int *dc) {

 /* If the left if free, we want to turn left.  If straight ahead is
    free, we just want to move.  If the right is free, we want to turn
    right.  Otherwise, we want to turn around. */

 if ((M[*r-1][*c-1]>>LeftSide (dir,*dr,*dc))%2) Left (dir,dr,dc);
 else if ((M[*r-1][*c-1]>>DirectSide (*dr,*dc))%2);
 else if ((M[*r-1][*c-1]>>RightSide (dir,*dr,*dc))%2) Right (dir,dr,dc);
 else {*dr = -*dr; *dc = -*dc;}
 *r += *dr; *c += *dc; /* Advancing */
}

/* Right and Left shift the orientation of the robot 90 degrees in
   that direction.  However, if dir is 0. the robot will rotate in
   the opposite direction. */
void Right (int dir,int *dr, int *dc) {

   int t = *dr;
  if (!dir) {Left (!dir,dr,dc);return;}
  *dr = *dc;
  *dc = -t;
}

void Left (int dir,int *dr, int *dc) {

   int t = *dc;
  if (!dir) {Right (!dir,dr,dc);return;}
  *dc = *dr;
  *dr = -t;
}

/* LeftSide, RightSide, and DirectSide return the bit position of the
   open/closed bit in the number corresponding to that particular side.
   if dir is 0, it returns the bit value of the opposite side. */
int LeftSide (int dir,int dr,int dc) {

 if (dir) {
  if (dc==1) return 0;
  if (dr==1) return 1;
  if (dc==-1) return 2;
  return 3;
 }
 if (dc==1) return 2;
 if (dr==1) return 3;
 if (dc==-1) return 0;
 return 1;
}

int RightSide (int dir,int dr, int dc) {

 return LeftSide (!dir,dr,dc);
}

int DirectSide (int dr, int dc) {

 if (dc==1) return 1;
 if (dr==1) return 2;
 if (dc==-1) return 3;
 return 0;
}