#include <cstdio>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

const int INF = INT_MAX / 2;
int dy[] = {1, -1, 0, 0};
int dx[] = {0, 0, -1, 1};

int h, w;
vector<vector<bool> > wall;

int minDist(int sy, int sx)
{
    vector<vector<bool> > check(2*h+1, vector<bool>(2*w+1, false));
    check[2*h-1][2*w-1] = true;
    queue<pair<int, int> > q;
    q.push(make_pair(2*h-1, 2*w-1));

    int ret = 0;
    while(!q.empty()){
        int m = q.size();
        while(--m >= 0){
            int y1 = q.front().first;
            int x1 = q.front().second;
            q.pop();
            if(y1 == sy && x1 == sx)
                return ret;

            for(int i=0; i<4; ++i){
                int y2 = y1 + dy[i];
                int x2 = x1 + dx[i];
                if(wall[y2][x2])
                    continue;
                y2 += dy[i];
                x2 += dx[i];
                if(check[y2][x2])
                    continue;
                check[y2][x2] = true;
                q.push(make_pair(y2, x2));
            }
        }
        ++ ret;
    }
    return INF;
}

int solve()
{
    vector<vector<int> > dp(2*h+1, vector<int>(2*w+1, INF));
    dp[2*h-1][2*w-1] = 0;
    multimap<int, pair<int, int> > mm;
    mm.insert(make_pair(0, make_pair(2*h-1, 2*w-1)));

    while(!mm.empty()){
        int cost = mm.begin()->first;
        int y = mm.begin()->second.first;
        int x = mm.begin()->second.second;
        mm.erase(mm.begin());
        if(cost > dp[y][x])
            continue;
        if(y == 1 && x == 1)
            return cost;

        for(int i=0; i<4; ++i){
            int y2 = y + dy[i];
            int x2 = x + dx[i];
            if(wall[y2][x2])
                continue;

            wall[y2][x2] = true;
            y2 += dy[i];
            x2 += dx[i];

            int cost2 = max(cost + 1, minDist(y2, x2));
            if(cost2 < dp[y2][x2]){
                dp[y2][x2] = cost2;
                mm.insert(make_pair(cost2, make_pair(y2, x2)));
            }

            y2 -= dy[i];
            x2 -= dx[i];
            wall[y2][x2] = false;
        }
    }

    return INF;
}

int main()
{
    for(;;){
        cin >> h >> w;
        if(h == 0)
            return 0;

        wall.assign(2*h+1, vector<bool>(2*w+1, false));
        for(int i=0; i<2*h+1; ++i)
            wall[i][0] = wall[i][2*w] = true;
        for(int i=0; i<2*w+1; ++i)
            wall[0][i] = wall[2*h][i] = true;

        for(int i=0; i<h; ++i){
            for(int j=0; j<w-1; ++j){
                int tmp;
                cin >> tmp;
                wall[2*i+1][2*j+2] = (tmp == 1);
            }
            if(i != h-1){
                for(int j=0; j<w; ++j){
                    int tmp;
                    cin >> tmp;
                    wall[2*i+2][2*j+1] = (tmp == 1);
                }
            }
        }

        int ret = solve();
        if(ret < INF)
            cout << ret << endl;
        else
            cout << -1 << endl;
    }
}

Measured memory_bytes: 1252