#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,_6,NAME,...) NAME
#define pr(...) GET_MACRO(__VA_ARGS__,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__)
#define Pr(a) (#a)<<"="<<(a)<<" "
#define pr1(a) cerr<<Pr(a)<<endl;
#define pr2(a,b) cerr<<Pr(a)<<Pr(b)<<endl;
#define pr3(a,b,c) cerr<<Pr(a)<<Pr(b)<<Pr(c)<<endl;
#define pr4(a,b,c,d) cerr<<Pr(a)<<Pr(b)<<Pr(c)<<Pr(d)<<endl;
#define pr5(a,b,c,d,e) cerr<<Pr(a)<<Pr(b)<<Pr(c)<<Pr(d)<<Pr(e)<<endl;
#define pr6(a,b,c,d,e,f) cerr<<Pr(a)<<Pr(b)<<Pr(c)<<Pr(d)<<Pr(e)<<Pr(f)<<endl;
#define double long double
using namespace std;
const int INF = 1e9;
const int mod = (1e9)+7;
const double EPS = 1e-8;
const double PI = 6.0 * asin(0.5);
typedef pair<int,int> P;
typedef long long ll;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
ostream& operator<<(ostream& o,P p){return o<<"("<<p.first<<","<<p.second<<")";}
istream& operator>>(istream& i,P &p){return i>>p.first>>p.second;}
ostream& operator<<(ostream& o,vector<auto> &a){int i=0;for(auto t:a)o<<(i++?" ":"")<<t;return o;}
istream& operator>>(istream& i,vector<auto> &a){for(auto &t:a)i>>t;return i;}
void prArr(auto a,string s=" "){int i=0;for(auto t:a)cout<<(i++?s:"")<<t;cout<<endl;}
const int N = 50;
int h,w;
int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};
int G[N][N][4];
int in(int x,int y){return !(x < 0 || y < 0 || x >= w || y >= h);}

int dis[N][N][N][N][4]; //goalからの距離
void bfs(int sy,int sx){
  memset(dis,-1,sizeof(dis));
  typedef tuple<int,int,int,int,int,int> T; // y, x, by, bx, dir, cost
  queue<T> Q;
  
  //broken door
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)
      for(int k=0;k<4;k++){
        dis[sy][sx][i][j][k] = 0;
        Q.push(T(sy,sx,i,j,k,0));
      }
  
  while(!Q.empty()){
    int y, x, by, bx, dir, cost;
    tie(y, x, by, bx, dir, cost) = Q.front(); Q.pop();
    
    for(int i=0;i<4;i++){
      int ny = y + dy[i];
      int nx = x + dx[i];
      int ncost = cost + 1;
      if(!in(nx,ny) || G[y][x][i] == 0 || dis[ny][nx][by][bx][dir] != -1) continue;
      if(x == bx && y == by && i == dir) continue;
      if(nx == bx && ny == by && i == (dir+2)%4) continue;
      dis[ny][nx][by][bx][dir] = ncost;
      Q.push(T(ny,nx,by,bx,dir,ncost));
    }
  }
  
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)
      for(int k=0;k<h;k++)
        for(int l=0;l<w;l++)
          for(int m=0;m<4;m++) if(dis[i][j][k][l][m] == -1) dis[i][j][k][l][m] = INF;
}

int calcCost(int y,int x,int d,int dir){
  if(!in(x,y)) return INF;
  int res = INF;
  Min(res, d + dis[y][x][y][x][dir]);
  return res;
}

int D[N][N][N*N], visited[N][N][N*N];
int dijkstra(int sy,int sx){
  typedef tuple<int,int,int,int> T; //cost, y, x, distance;

  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)
      for(int k=0;k<=h*w;k++) D[i][j][k] = INF, visited[i][j][k] = 0;
  
  priority_queue<T,vector<T>,greater<T> > Q;
  Q.push(T(0,sy,sx,0));
  D[sy][sx][0] = 0;

  int res = INF;
  while(!Q.empty()){
    int cost, y, x, d;
    tie(cost,y, x, d) = Q.top(); Q.pop();
    if(visited[y][x][d]++) continue;
    if(x == w-1 && y == h-1) {
      Min(res, max(cost, d));
      continue;
    }

    for(int i=0;i<4;i++){
      int nx = x + dx[i];
      int ny = y + dy[i];
      int nd = d + 1;
      int a = cost;
      int b = calcCost(y, x, d, i);
      int ncost = max(a, b);
      if(!in(nx,ny) || G[y][x][i] == 0 || D[ny][nx][nd] <= ncost) continue;
      D[ny][nx][nd] = ncost;
      Q.push(T(ncost,ny,nx,nd));
    }
  }
  if(res == INF) return -1;
  return res;
}


signed main(){
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  while(1){
    cin>>h>>w;
    if(h == 0 && w == 0) break;
    for(int i=0;i<=h;i++)
      for(int j=0;j<=w;j++)
        for(int k=0;k<4;k++) G[i][j][k] = 1;

    for(int i=0;i<h*2-1;i++){
      for(int j=0;j<w - !(i%2);j++){
        int ng;
        cin>>ng;
        int x = j, y = i/2;
        if(i%2 == 0 && ng) G[y][x][1] = G[y][x+1][3] = 0;
        if(i%2 == 1 && ng) G[y][x][2] = G[y+1][x][0] = 0;
      }
    }

    bfs(h-1, w-1);
    
    int ans = dijkstra(0, 0);
    cout<<ans<<endl;
  }
  return 0;
}



Measured memory_bytes: 116880