#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];
int dp[2000][33][33]; // [step][y][x] 最悪でも2000は越えないだろう…
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;
    }
};


int bfs(int sx, int sy){
    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;

    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( tx < 0 || tx >= 2*w-1 || ty >= 2*h-1 || ty < 0 ) continue;
            if( field[ty][tx] == '1' ) continue;

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

    return memo[h-1][w-1];
}


void setBrokenDoorToAllShortestPath(){
    int i,j,k;

    // 通れなかった場所からの最短距離を全て記録する
    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( tx < 0 || tx >= 2*w-1 || ty >= 2*h-1 || ty < 0 ) continue;
                if( field[ty][tx] == '1' ) continue;
                field[ty][tx] = '1';
                path[k][i][j] = bfs(j, i);
                field[ty][tx] = '0';
            }
        }
    }
}



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

        setBrokenDoorToAllShortestPath();

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

            //cout << "step = " << step << ", q.size = " << q.size() << endl;

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

                if( dp[step + 1][y + dy[k]][x + dx[k]] > nextWorstStep ){
                    q.push(state(x + dx[k], y + dy[k], step + 1, nextWorstStep));
                }

            }
        }

        int ans = inf;
        for(k=0; k<500; k++) ans = min(ans, dp[k][h-1][w-1]);

        cout << (ans == inf ? -1 : ans) << endl;
    }

    return 0;
}

Measured memory_bytes: 3228