#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
typedef pair<int, i_i> iii;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define down 0
#define right 1
#define up 2
#define left 3
//const ll mod = 1000000007;
int dh[4] = {1, 0, -1, 0};
int dw[4] = {0, 1, 0, -1};
// down, right, up, left
int can[4][35][35];
int dist[2][35][35];
int H, W;
int dp[35][35];
vector<i_i> query;
void initialize(int index) {
    for(int h = 0; h <= 31; h++) {
        for(int w = 0; w <= 31; w++) dist[index][h][w] = INF;
    }
}
bool chmax(int &a, int b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

bool chmin(int &a, int b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

void BFS(int index, int sh, int sw) {
    initialize(index);
    dist[index][sh][sw] = 0;
    queue<i_i> que;
    que.push({sh, sw});
    while(!que.empty()) {
        i_i now = que.front();
        que.pop();
        if(index == 0) query.push_back(now);
        //cerr << "SEARCHING: " << now.first << " " << now.second << endl;
        for(int k = 0; k < 4; k++) {
            if(can[k][now.first][now.second] == 1) {
                //cerr << "CAN'T MOVE TO " << k << endl;
                continue;
            }
            int newh = now.first + dh[k];
            int neww = now.second + dw[k];
            //cerr << newh << " " << neww << endl;
            if(newh <= 0 || newh > H || neww <= 0 || neww > W) continue;
            if(chmin(dist[index][newh][neww], dist[index][now.first][now.second] + 1)) {
                que.push({newh, neww});
            }
        }
    }
    return;
}

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(cin >> H >> W) {
        if(H == 0) break;
        for(int h = 1; h <= H; h++) {
            for(int w = 1; w < W; w++) {
                cin >> can[right][h][w];
                can[left][h][w+1] = can[right][h][w];
            }
            if(h == H) break;
            for(int w = 1; w <= W; w++) {
                cin >> can[down][h][w];
                can[up][h+1][w] = can[down][h][w];
            }
        }
        /*
        for(int k = 0; k < 4; k++) {
            for(int h = 1; h <= H; h++) {
                for(int w = 1; w <= W; w++) cerr << can[k][h][w] << " ";
                cerr << endl;
            }
            cerr << endl;
        }
        */
        initialize(0);
        query.clear();
        BFS(0, H, W);
        for(int h = 1; h <= H; h++) {
            for(int w = 1; w <= W; w++) {
                dp[h][w] = INF;
            }
        }
        dp[H][W] = 0;
        priority_queue<iii> que;
        que.push({0, {H, W}});
        while(!que.empty()) {
            //cerr << query[i].first << " " << query[i].second << endl;
            int h = que.top().second.first;
            int w = que.top().second.second;
            que.pop();
            for(int k = 0; k <= 3; k++) {
                if(can[k][h][w] == 1) continue;
                int newh = h + dh[k];
                int neww = w + dw[k];
                if(newh <= 0 || newh > H || neww <= 0 || neww > W) continue;
                //if(dist[0][newh][neww] >= dist[0][h][w]) continue;
                //chmax(dp[h][w], 1 + dp[newh][neww]);
                int nowcost = dp[h][w] + 1;
                can[k][h][w] = 1;
                can[(k+2)%4][newh][neww] = 1;
                BFS(1, H, W);
                /*
                cerr << "---{" << h << ", " << w << "} {" << newh << ", " << neww << "}---" << endl;
                for(int h = 1; h <= H; h++) {
                    for(int w = 1; w <= W; w++) {
                        cerr << dist[1][h][w] << " ";
                    }
                    cerr << endl;
                }
                */
                chmax(nowcost, dist[1][newh][neww]);
                if(chmin(dp[newh][neww], nowcost)) {
                    que.push({nowcost, {newh, neww}});
                }
                //chmax(dp[h][w], dist[1][h][w]);
                can[k][h][w] = 0;
                can[(k+2)%4][newh][neww] = 0;
            }
            //cerr << h << " " << w << " " << dp[h][w] << endl;
        }
        /*
        for(int h = 1; h <= H; h++) {
            for(int w = 1; w <= W; w++) {
                cerr << dist[0][h][w] << " ";
            }
            cerr << endl;
        }
        */
       if(dp[1][1] == INF) dp[1][1] = -1;
       cout << dp[1][1] << endl;
    }
    return 0;
}


Measured memory_bytes: 3212