#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 32
#define SHORT_NUM 32000

enum Type{
	UNDER,
	RIGHT,
};

struct Door{
	Door(int arg_row,int arg_col,Type arg_type){
		row = arg_row;
		col = arg_col;
		type = arg_type;
	}
	int row,col;
	Type type;
};

struct Wall{
	void set(bool arg_under_wall,bool arg_right_wall){
		under_wall = arg_under_wall;
		right_wall = arg_right_wall;
	}
	bool under_wall,right_wall;
	int under_index,right_index;
};

struct Info{
	Info(int arg_row,int arg_col,short arg_sum_cost){
		row = arg_row;
		col = arg_col;
		sum_cost = arg_sum_cost;
	}
	bool operator<(const struct Info &arg) const{ //★総コストの昇順(PQ)★
		return sum_cost > arg.sum_cost;
	}
	int row,col;
	short sum_cost;
};

int H,W;
int num_door;
int diff_row[4] = {-1,0,0,1},diff_col[4] = {0,-1,1,0};
short min_dist[1740][NUM][NUM],final_min_dist[NUM][NUM];
vector<Door> DOOR;
Wall wall[NUM][NUM];

bool rangeCheck(int row,int col){
	if(row >= 1 && row <= H && col >= 1 && col <= W){
		return true;
	}else{
		return false;
	}
}

void dijkstra(int door_index){

	for(int row = 1; row <= H; row++){
		for(int col = 1; col <= W; col++){
			min_dist[door_index][row][col] = SHORT_NUM;
		}
	}

	min_dist[door_index][H][W] = 0;
	priority_queue<Info> Q;

	Q.push(Info(H,W,0));

	int adj_row,adj_col;
	short next_cost;

	while(!Q.empty()){

		if(Q.top().sum_cost > min_dist[door_index][Q.top().row][Q.top().col]){

			Q.pop();
		}else{

			for(int i = 0; i < 4; i++){

				adj_row = Q.top().row+diff_row[i];
				adj_col = Q.top().col+diff_col[i];

				if(!rangeCheck(adj_row,adj_col))continue;

				next_cost = Q.top().sum_cost+1;

				switch(i){
				case 0: //上へ移動
					if(wall[adj_row][adj_col].under_wall){
						next_cost = -1;
					}
					break;
				case 1: //左へ移動
					if(wall[adj_row][adj_col].right_wall){
						next_cost = -1;
					}
					break;
				case 2: //右
					if(wall[Q.top().row][Q.top().col].right_wall){
						next_cost = -1;
					}
					break;
				case 3: //下
					if(wall[Q.top().row][Q.top().col].under_wall){
						next_cost = -1;
					}
					break;
				}
				if(next_cost == -1)continue;

				if(min_dist[door_index][adj_row][adj_col] > next_cost){
					min_dist[door_index][adj_row][adj_col] = next_cost;
					Q.push(Info(adj_row,adj_col,next_cost));
				}
			}

			Q.pop();
		}
	}

}

void func(){

	DOOR.clear();
	num_door = 0;

	//マップの左の壁
	for(int row = 0; row <= H; row++){
		wall[row][0].right_wall = true;
	}

	//マップの下の壁
	for(int col = 1; col <= W; col++){
		wall[H][col].under_wall = true;
	}

	//マップの右の壁
	for(int row = 1; row <= H; row++){
		wall[row][W].right_wall = true;
	}

	//マップの上の壁
	for(int col = 1; col <= W; col++){
		wall[0][col].under_wall = true;
	}

	wall[0][1].under_wall = false; //入口
	wall[H][W].under_wall = false; //出口

	int tmp;

	for(int row = 1; row <= H; row++){

		//第row行の、垂直方向の壁情報
		for(int col = 1; col <= W-1; col++){
			scanf("%d",&tmp);

			if(tmp == 1){
				wall[row][col].right_wall = true; //★ドアがないなら壁
			}else{
				wall[row][col].right_wall = false; //★★ドア有り★★
				wall[row][col].right_index = num_door; //★このドアが壊れた時の、min_distのインデックスを記録★
				DOOR.push_back(Door(row,col,RIGHT));
				num_door++;
			}
		}

		if(row == H)break;

		//第row行の、部屋の下の壁情報
		for(int col = 1; col <= W; col++){
			scanf("%d",&tmp);

			if(tmp == 1){
				wall[row][col].under_wall = true; //★ドアがないなら壁
			}else{
				wall[row][col].under_wall = false;
				wall[row][col].under_index = num_door;
				DOOR.push_back(Door(row,col,UNDER));
				num_door++;
			}
		}
	}

	//★★あるドアが壊れている時の、ゴールからの最小距離を全探索
	for(int loop = 0; loop < num_door; loop++){

		if(DOOR[loop].type == RIGHT){
			wall[DOOR[loop].row][DOOR[loop].col].right_wall = true;
		}else{
			wall[DOOR[loop].row][DOOR[loop].col].under_wall = true;
		}

		dijkstra(loop);

		if(DOOR[loop].type == RIGHT){
			wall[DOOR[loop].row][DOOR[loop].col].right_wall = false;
		}else{
			wall[DOOR[loop].row][DOOR[loop].col].under_wall = false;
		}
	}

	//総まとめのダイクストラ
	for(int row = 1; row <= H; row++){
		for(int col = 1; col <= W; col++){
			final_min_dist[row][col] = SHORT_NUM;
		}
	}

	priority_queue<Info> Q;
	final_min_dist[H][W] = 0;
	Q.push(Info(H,W,0));

	int adj_row,adj_col,tmp_index;
	short next_cost;

	while(!Q.empty()){

		if(Q.top().sum_cost > final_min_dist[Q.top().row][Q.top().col]){

			Q.pop();

		}else{

			for(int i = 0; i < 4; i++){

				adj_row = Q.top().row+diff_row[i];
				adj_col = Q.top().col+diff_col[i];

				if(!rangeCheck(adj_row,adj_col))continue;

				next_cost = Q.top().sum_cost+1;

				switch(i){
				case 0: //上へ移動
					if(wall[adj_row][adj_col].under_wall){

						next_cost = -1;

					}else{
						tmp_index = wall[adj_row][adj_col].under_index;
					}
					break;
				case 1: //左へ移動
					if(wall[adj_row][adj_col].right_wall){

						next_cost = -1;

					}else{
						tmp_index = wall[adj_row][adj_col].right_index;
					}
					break;
				case 2: //右
					if(wall[Q.top().row][Q.top().col].right_wall){

						next_cost = -1;

					}else{
						tmp_index = wall[Q.top().row][Q.top().col].right_index;
					}
					break;
				case 3: //下
					if(wall[Q.top().row][Q.top().col].under_wall){

						next_cost = -1;

					}else{

						tmp_index = wall[Q.top().row][Q.top().col].under_index;
					}
					break;
				}
				if(next_cost == -1)continue;

				/*★ある場所にゴールから到達するコストにおいて、任意の壁が壊れている場合と、そうでない場合の大きいコストを採用★*/
				next_cost = max(next_cost,min_dist[tmp_index][adj_row][adj_col]);

				if(final_min_dist[adj_row][adj_col] > next_cost){
					final_min_dist[adj_row][adj_col] = next_cost;
					Q.push(Info(adj_row,adj_col,next_cost));
				}
			}
			Q.pop();
		}
	}

	if(final_min_dist[1][1] == SHORT_NUM){
		printf("-1\n");
	}else{
		int ans = (int)final_min_dist[1][1];
		printf("%d\n",ans);
	}
}


int main(){

	while(true){
		scanf("%d %d",&H,&W);
		if(H == 0 && W == 0)break;

		func();
	}

	return 0;
}



Measured memory_bytes: 6720