/* 
   AOJ 1166
   Amazing Mazes
   2015/8/16
*/

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

#define MAX_INFO_H 61
#define MAX_INFO_W 61
#define MAX_H 31
#define MAX_W 31

int min = INT_MAX, width, height, dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

char meize_info[MAX_INFO_W][MAX_INFO_H];




/* #define QUEUE_MAX 10000 */
/* int queue[QUEUE_MAX], pp = 0, gp = 0; */
/* void init() { pp = 0; gp = 0; } */
/* void put(int x) { queue[pp] = x; pp = (pp + 1) % QUEUE_MAX; } */
/* int get() { int t = queue[gp]; gp = (gp + 1) % QUEUE_MAX; return t; } */
/* int empty() { return pp == gp; } */

/* int solve() */
/* { */
/*   int x = 0, y = 0, count = 0, dx, dy; */
/*   init(); */
/*   push(x), push(y), push(count); */

/*   while(!empty()){ */
/*     count = get(), y = get(), x = get(); */
/*     visited[x, y] = 1; */

/*     if(isGoal(x, y)) return count; */

/*     for(dx = -1; dx <=1; dx++) */
/*       for(dy = -1; dy <= 1; dy++){ */
/* 	if(visitable(x, y, x+dx, y+dy) && !visited[x+dx][y+dy]) */
/* 	  push(x+dx), push(y+dy), push(count); */
/*       } */
/*   } */

/*   return -1; */
/* } */




struct node
{
  int **meize;
  int x, y, cnt;
  struct node *link;
};

struct node *head;

void init()
{
  head = NULL;
}

int empty()
{
  return head == NULL;
}

void put(int **n_meize, int n_x, int n_y, int n_cnt)
{
  struct node *new_node = malloc(sizeof(struct node)), *next = head;

  if(head == NULL)
    {
      head = new_node;
    }
  else
    {
      while(next->link != NULL)
	{
	  if(next->x == n_x && next->y == n_y)
	    {
	      if(next->cnt < n_cnt)
		{
		  return ;
		}
	      else
		{
		  next->cnt = n_cnt;
		  next->meize = n_meize;
		  next->x = n_x;
		  next->y = n_y;
		  return ;
		}
	    }
	  next = next->link;
	}
      next->link = new_node;
    }

  new_node->meize = n_meize;
  new_node->x = n_x;
  new_node->y = n_y;
  new_node->cnt = n_cnt;
  new_node->link = NULL;
}

struct node get()
{
  struct node *get_p = head;
  struct node get_node = *head;
  
  head = head->link;

  free(get_p);

  return get_node;
}


void dfs(int x, int y, int** meize, int cnt)
{
  int i, j, next_x = 0, next_y = 0;
  meize[y][x] = 1;
  cnt++;

  /* printf("\n"); */

  /* for(i = 0; i < height; i++) */
  /*   { */
  /*     for(j = 0; j < width; j++) */
  /* 	{ */
  /* 	  printf("%d", meize[i][j]); */
  /* 	} */
  /*     printf("\n"); */
  /*   } */


  if(x == width - 1 && y == height - 1)
    {
      if(min > cnt)
	{
	  min = cnt;
	}
      return ;
    }
  for(i = 0; i < 4; i++)
    {
      next_y = y + dir[i][0];
      next_x = x + dir[i][1];

      if(0 <= next_x && next_x <= width - 1 && 0 <= next_y && next_y <= height - 1 && meize[next_y][next_x] != 1)
	{
	  /* printf("\n"); */
	  /* printf("\t%d\t%3d%3d", i, x, y); */

	  switch(i)
	    {
	    case 0:
	      /* down */
	      if(meize_info[y * 2 + 1][x * 2] != '1')
		{
		  dfs(next_x, next_y, meize, cnt);
		}
	      break;
	    case 1:
	      /* right */
	      if(meize_info[y * 2][x * 2 + 1] != '1')
		{
		  dfs(next_x, next_y, meize, cnt);
		}
	      break;

	    case 2:
	      /* up */
	      if(meize_info[y * 2 - 1][x * 2] != '1')
		{
		  dfs(next_x, next_y, meize, cnt);
		}
	      break;
	    case 3:
	      /* left */
	      if(meize_info[y * 2][x * 2 - 1] != '1')
		{
		  dfs(next_x, next_y, meize, cnt);
		}
	      break;
	    }
	}
    }
}

void traverse()
{
  struct node *next;
  printf("----queue-top----\n");
  for(next = head; next != NULL; next = next->link)
    {
      printf("x = %d, y = %d, cnt = %d\n", next->x, next->y, next->cnt);
    }
  printf("----queue-bottom----\n");
}

void bfs(int x, int y, int **meize, int cnt)
{
  int i, j, next_x = 0, next_y = 0;
  struct node present_status;

  init();
  /* meize[y][x] = 1; */
  /* cnt++; */
  put(meize, x, y, cnt);

  while(!empty())
    {
      //traverse();
      present_status = get();
      present_status.meize[present_status.y][present_status.x] = 1;
      present_status.cnt++;
      
      //      printf("x = %d, y = %d\ncnt = %d", present_status.x, present_status.y, present_status.cnt);

      /* printf("\n"); */
      /* for(i = 0; i < height; i++) */
      /* 	{ */
      /* 	  for(j = 0; j < width; j++) */
      /* 	    { */
      /* 	      printf("%d", present_status.meize[i][j]); */
      /* 	    } */
      /* 	  printf("\n"); */
      /* 	} */

      if(present_status.x == width - 1 && present_status.y == height - 1)
	{
	  if(min > present_status.cnt)
	    {
	      min = present_status.cnt;
	    }
	  continue;
	}
      for(i = 0; i < 4; i++)
	{
	  //  printf("\ni = %d\n", i);
	  next_y = present_status.y + dir[i][0];
	  next_x = present_status.x + dir[i][1];

	  if(0 <= next_x && next_x <= width - 1 && 0 <= next_y && next_y <= height - 1 && present_status.meize[next_y][next_x] != 1)
	    {
	      switch(i)
		{
		case 0:
		  /* down */
		  if(meize_info[present_status.y * 2 + 1][present_status.x * 2] != '1')
		    {
		      //		      printf("put->down\n");
		      //		      present_status.meize[next_y][next_x] = 1;
		      put(present_status.meize, next_x, next_y, present_status.cnt);
		    }
		  break;
		case 1:
		  /* right */
		  if(meize_info[present_status.y * 2][present_status.x * 2 + 1] != '1')
		    {
		      //		      printf("put->right\n");
		      // present_status.meize[next_y][next_x] = 1;
		      put(present_status.meize, next_x, next_y, present_status.cnt);
		    }
		  break;
		case 2:
		  /* up */

		  if(meize_info[present_status.y * 2 - 1][present_status.x * 2] != '1')
		    {
		      //		      printf("put->up\n");
		      //		      present_status.meize[next_y][next_x] = 1;
		      put(present_status.meize, next_x, next_y, present_status.cnt);
		    }
		  break;
		case 3:
		  /* left */

		  if(meize_info[present_status.y * 2][present_status.x * 2 - 1] != '1')
		    {
		      //		      printf("put->left\n");
		      //		      present_status.meize[next_y][next_x] = 1;
		      put(present_status.meize, next_x, next_y, present_status.cnt);
		    }
		  break;
		}
	    }
	}
    }
}

void ans_f()
{
  int** meize, i, j;

  meize = malloc(sizeof(int *) * height);

  for(i = 0; i < height; i++)
    {
      meize[i] = malloc(sizeof(int) * width);
    }
  /* printf("hoge"); */
  /* fflush(stdout); */
  /*
    start == 0, 0
    goal == width - 1, height - 1
  */

  /* printf("%c\n", meize_info[0][0]); */
  /* fflush(stdout); */

  /* for(i = 0; i < 2 * height - 1; i++) */
  /*   { */
  /*     printf("%s\n", meize_info[i]); */
  /*     fflush(stdout); */
  /*   } */

  for(i = 0; i < height; i++)
    {
      for(j = 0; j < width; j++)
	{
	  meize[i][j] = 0;
	}
    }

  bfs(0, 0, meize, 0);

  //  dfs(0, 0, meize, 0);
  if(min == INT_MAX)
    {
      min = 0;
    }
}

int main(void)
{
  int i, j;
  char dust;

  while(1)
    {

      min = INT_MAX;

      for(i = 0; i < MAX_INFO_W; i++)
	{
	  for(j = 0; j < MAX_INFO_H; j++)
	    {
	      meize_info[i][j] = '\0';
	    }
	}

      scanf("%d %d", &width, &height);
      
      if(width == 0 && height == 0)
	{
	  break;
	}

      scanf("%c", &dust);

      for(i = 0; i < 2 * height - 1; i++)
	{
	  gets(meize_info[i]);
	}
      
      /* for(i = 0; i < 2 * height - 1; i++) */
      /* 	{ */
      /* 	  printf("%s\n", meize_info[i]); */
      /* 	} */

      ans_f();
      printf("%d\n", min);
 
    }
  return 0;
}

Measured memory_bytes: 1652