#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 block[32][32][4];
int path[4][32][32]; // 未処理の場合は -1, ゴールできないときは inf
int dp[900][32][32]; // [step][y][x] 最悪でも500は越えないだろう…
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;
}

bool isCut(int step, int x, int y, int nextWorstStep){
    int i;
    for(i=0; i<=step; i++) if( dp[i][y][x] <= nextWorstStep ) break;
    return (i > step);
}

int solve(){
    int i,k;
    int cutOff = inf; // 枝刈り用
    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 > 900 ) break;

        if( dp[step][y][x] <= wstep ) continue;
        dp[step][y][x] = wstep;

        if( y == h-1 && x == w-1 ) return dp[step][h-1][w-1];

        
        if( cutOff <= wstep ) continue;

        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]);

            // step + 1以下の最小値管理をうまくしないと、上で枝刈りしても、ここでキューに突っ込んでるからlogn時間遅くなる
            // ここをO(1)にしたい、むきー
            if( isCut(step + 1, x + dx[k], y + dy[k], nextWorstStep) ){
                q.push(state(x + dx[k], y + dy[k], step + 1, nextWorstStep));

                
                // 仮に移動先がゴールだった場合、枝狩り変数を持つことができる
                if( y + dy[k] == h-1 && x + dx[k] == w-1 ){
                    cutOff = min(cutOff, 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][0], &dp[0][0][0] + 900*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: 4584