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


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;
    int memo[33][33];
    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 tx = 2*x + dx[k];
            int ty = 2*y + dy[k];
            if( !inside(tx, ty) || field[ty][tx] == '1' ) continue;

            if( memo[y + dy[k]][x + dx[k]] == -1 ){
                memo[y + dy[k]][x + dx[k]] = s + 1;
                if( gy == y + dy[k] && gx == x + dx[k] ) return s + 1;
                q.push(make_pair(x + dx[k], y + dy[k]));
            }
        }
    }

    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( wstep == inf || step > 500 ) 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 ){
            //cutCount++;
            continue;
        }

        for(k=0; k<4; k++){
            int tx = 2*x + dx[k];
            int ty = 2*y + dy[k];
            if( !inside(tx,ty) || field[ty][tx] == '1' ) continue;
                
            // ドアが壊れてたときの計算
            int nextWorstStep = inf;

            // まだBFSで調べてないので調べる
            if( path[k][y][x] == -1 ){
                field[ty][tx] = '1';
                path[k][y][x] = bfs(x, y, w-1, h-1);
                field[ty][tx] = '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] += " ";
        }

        // init
        for(k=0; k<500; k++){
            for(i=0; i<33; i++){
                for(j=0; j<33; j++){
                    dp[k][i][j] = inf;
                }
            }
        }
        memset(path, -1, sizeof(path));

        cout << solve() << endl;
    }

    return 0;
}

Measured memory_bytes: 3100