#include <iostream>
#include <queue>
#include <string>
#include <cstdio>
#include <cstring>
#include <climits>
using namespace std;

const int dx[] = {0, 1, 0, -1}; //上右下左
const int dy[] = {-1, 0, 1, 0};
const int inf = 1<<20;

int w,h;
int DP[32][32], usedCard[32][32];
int block[32][32][4];
int path[4][32][32]; // 未処理の場合は -1, ゴールできないときは inf
string field[70];

struct state{
    int x,y;
    int step;
    int worstStep;
    state(int _x, int _y, int s, int w){
        x = _x;
        y = _y;
        step = s;
        worstStep = w;
    }
    bool operator<(const state& a)const{
        if( worstStep == a.worstStep ) return step > a.step;
        return worstStep > a.worstStep;
    }
};


inline bool inside(int x, int y){
    return !( x < 0 || x >= 2*w-1 || y >= 2*h-1 || y < 0 );
}


int bfs(int sx, int sy, int gx, int gy){
    int k;
    char memo[32][32];
    queue<pair<int,int> > q;

    memset(memo, -1, sizeof(memo));
    q.push(make_pair(sx,sy));
    memo[sy][sx] = 0;

    if( sx == gx && sy == gy ) return 0;

    while( !q.empty() ){
        int x = q.front().first;
        int y = q.front().second;
        int s = memo[y][x];
        q.pop();

        for(k=0; k<4; k++){
            int nx = x + dx[k], ny = y + dy[k];
            if( !block[y][x][k] && memo[ny][nx] == -1 ){
                memo[ny][nx] = s + 1;
                if( gy == ny && gx == nx ){
                    return s + 1;
                }
                q.push(make_pair(nx, ny));
            }
        }
    }
    
    return inf;
}


int solve(){
    int i,k;
    priority_queue<state> q;
    q.push(state(0,0,0,0));

    while( !q.empty() ){
        int x = q.top().x;
        int y = q.top().y;
        int step = q.top().step;
        int wstep = q.top().worstStep;
        q.pop();

        if( step > 200 ) break;

        if( y == h-1 && x == w-1 ) return wstep;

        for(k=0; k<4; k++){
            if( block[y][x][k] ) continue;
                
            // ドアが壊れてたときの計算
            int nextWorstStep = inf;

            // まだBFSで調べてないので調べる
            if( path[k][y][x] == -1 ){
                block[y][x][k] = 1;
                path[k][y][x] = bfs(x, y, w-1, h-1);
                block[y][x][k] = 0;
            }

            if( path[k][y][x] == inf ) continue; // ゴールできない

            nextWorstStep = max(wstep, step + path[k][y][x]);

            int nx = x + dx[k], ny = y + dy[k];

            if( DP[ny][nx] > nextWorstStep ){
                DP[ny][nx] = nextWorstStep;
                usedCard[ny][nx] = step + 1;
                q.push(state(nx, ny, step + 1, nextWorstStep));
            }
            else if( step + 1 < usedCard[ny][nx] ){
                // nextWorstStepが最も小さいものから処理されるから、2度目以降のnextWorstStepは必ず大きい。よって、
                usedCard[ny][nx] = step + 1;
                q.push(state(nx, ny, step + 1, nextWorstStep));
            }
        }
    }
    return -1;
}



int main(){
    int i,j,k;

    while( cin >> h >> w, h|w ){
        cin.ignore();

        // input
        for(i=0; i<2*h-1; i++){
            getline(cin, field[i]);
            if( i % 2 == 0 ) field[i] += " ";
        }
        fill(&DP[0][0], &DP[0][0] + 32*32, inf);
        fill(&usedCard[0][0], &usedCard[0][0] + 32*32, inf);
        memset(path, -1, sizeof(path));

        // 通れない場所を予め調べておく
        for(i=0; i<h; i++){
            for(j=0; j<w; j++){
                for(k=0; k<4; k++){
                    int tx = 2*j + dx[k];
                    int ty = 2*i + dy[k];
                    if( !inside(tx, ty) || field[ty][tx] == '1' ){
                        block[i][j][k] = 1;
                    }
                    else{
                        block[i][j][k] = 0;
                    }
                }
            }
        }
        cout << solve() << endl;
    }

    return 0;
}

Measured memory_bytes: 984