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

#define BUF_SIZE ROW_MAX*3
#define ROW_MAX 30
#define COL_MAX 30

int get_int2(int *a1, int *a2) {
#ifdef BUF_SIZE
  char line[BUF_SIZE];
  if(!fgets(line, BUF_SIZE, stdin)) return -1;
  sscanf(line, "%d %d", a1, a2);
#else
#error
#endif
  return 0;
}

// <arr[0]> <arr[1]> .. <arr[size-1]>
int fget_array(char *arr, int size) {
#ifdef BUF_SIZE
    char line[BUF_SIZE];
    char *tmpbuf = line;
    int i;
    if(!fgets(line, BUF_SIZE, stdin)) return -1;
    for(i = 0; i < size; i++) {
        char *tmp = strtok(tmpbuf, " ");
        arr[i] = strtol(tmp, NULL, 10);
        tmpbuf = NULL;
    }
#else
#error
#endif
    return 0;
}

struct point2d {
    int row;
    int col;
};

struct point2d dist4[4] = {
    { 0, 1 },
    { 1, 0 },
    { 0, -1 },
    { -1, 0 }
};

enum dist_label {
    E_RIGHT = 0,
    E_BOTTOM = 1,
    E_LEFT = 2,
    E_UP = 3,
};


int is_equal(struct point2d p1, struct point2d p2) {
    return p1.row == p2.row && p1.col == p2.col;
}
static struct point2d queue[ROW_MAX*COL_MAX];
static int q_start = 0;
static int q_end = 0;
void enqueue(struct point2d p) {
    queue[q_end++] = p;
}

struct point2d dequeue(void) {
    return queue[q_start++];
}

int is_empty(void) {
    return q_start == q_end;
}
void init_queue(void) {
    q_start = q_end = 0;
}

#define SET_MAX 100
int main(void) {
    int ans[SET_MAX] = {0};
    int idx = -1;
    while(1) {
        init_queue();
        idx++;
        int row, col;
        get_int2(&col, &row);
        if(col+row == 0) break;
        int i, j;
        // start: (1, 1), goal: (row-1, col-1)
        char passed[ROW_MAX+2][COL_MAX+2][4] = {0};
        char buf[COL_MAX+3];
        for(i = 1; i <= row; i++) {
            fget_array(&buf[1], col-1);
            for(j = 1; j < col; j++) {
                passed[i][j][E_RIGHT] = passed[i][j+1][E_LEFT] = (!buf[j]);
            }

            if(i == row) break;
            fget_array(&buf[1], col);
            for(j = 1; j <= col; j++) {
                passed[i][j][E_BOTTOM] = passed[i+1][j][E_UP] = (!buf[j]);
            }
        }
        // boundary
        for(i = 1; i <= row; i++) {
            passed[i][1][E_LEFT] = 0;
            passed[i][col][E_RIGHT] = 0;
        }
        for(i = 1; i <= col; i++) {
            passed[1][i][E_UP] = 0;
            passed[row][i][E_BOTTOM] = 0;
        }

        int cnt_map[ROW_MAX+2][COL_MAX+2] = {0};
        struct point2d start = {1, 1};
        enqueue(start);
        cnt_map[start.row][start.col] = 1;
        struct point2d goal = {row, col};
        while(!is_empty()) {
            struct point2d p = dequeue();
#ifdef DEBUG
            printf("%d, %d\n", p.row, p.col);
#endif
            if(is_equal(p, goal)) {
                ans[idx] = cnt_map[p.row][p.col];
                break;
            }
            for(i = 0; i < 4; i++) {
                if(!passed[p.row][p.col][i]) continue;
                struct point2d np = {
                    p.row + dist4[i].row,
                    p.col + dist4[i].col
                };
                if(!cnt_map[np.row][np.col]) {
                    cnt_map[np.row][np.col] = cnt_map[p.row][p.col] + 1;
                    enqueue(np);
                }
            }
        }
    }
    int i;
    for(i = 0; i < idx; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}



Measured memory_bytes: 1988