// AOJ 1178 A Broken Door
// 2018.4.24 bal4u

#include <stdio.h>
#include <string.h>

// バッファを経ずstdinから数値を得る
//#define getchar_unlocked()  getchar()
int in()
{
	int n = 0, c = getchar_unlocked();
	while (c <= ' ') c = getchar_unlocked();
	do n = 10*n + (c & 0xf), c = getchar_unlocked(); while (c >= '0');
	return n;
}
 
#define INF 0xff
typedef unsigned char uchar;

typedef struct { uchar r, c, t; } QUE;
QUE que[905]; int top, end;
uchar hi[30][30], tr[30][30][4], tc[30][30][4];
uchar dist[30][30], cost[30][30], cost2[30][30];

int calc(int h, int w)
{
	int i, r, c, t, nr, nc;
	int ll, rr, mi;

	ll = cost[0][0], rr = INF;
	while (ll+1 < rr) {
		mi = (ll+rr) >> 1;

		memset(dist, INF, sizeof(dist));
		dist[0][0] = 0;
		que[0].r = 0, que[0].c = 0, que[0].t = 0, top = 0, end = 1;
		while (top != end) {
			r = que[top].r, c = que[top].c, t = que[top++].t;
			if (r == h && c == w) break;
			if (dist[r][c] < t) continue;
			for (i = 0; i < hi[r][c]; i++) {
				nr = tr[r][c][i], nc = tc[r][c][i];
				if (cost[nr][nc] + t+1 >= mi) continue;
				if (dist[nr][nc] > t+1)	{
					dist[nr][nc] = t+1;
					que[end].r = nr, que[end].c = nc, que[end++].t = t+1;
				}
			}
		}
		if (dist[h][w] < INF) rr = mi; else ll = mi;
	}
	if (rr == INF) rr = -1;
	return rr;
}

int main()
{
	int h, w, r, c, t, i;
	int r0, c0, nr, nc;

	while (h = in()) {
		w = in();
		memset(hi, 0, sizeof(hi));

		for (r = 0; r < h; r++) {
			for (c = 1; c < w; c++) if (in() == 0) {
				t = hi[r][c-1]++, tr[r][c-1][t] = r, tc[r][c-1][t] = c;
				t = hi[r][c  ]++, tr[r][c  ][t] = r, tc[r][c  ][t] = c-1;
			}
			if (r == h-1) break;
			for (c = 0; c < w; c++) if (in() == 0) {
				t = hi[r  ][c]++, tr[r  ][c][t] = r+1, tc[r  ][c][t] = c;
				t = hi[r+1][c]++, tr[r+1][c][t] = r,   tc[r+1][c][t] = c;
			}
		}

		memset(cost,  INF, sizeof(cost));
		memset(cost2, INF, sizeof(cost2));
		for (r0 = 0; r0 < h; r0++) for (c0 = 0; c0 < w; c0++) {
			memset(dist, INF, sizeof(dist));
			dist[h-1][w-1] = 0;
			que[0].r = h-1, que[0].c = w-1, que[0].t = 0, top = 0, end = 1;
			while (top != end) {
				r = que[top].r, c = que[top].c, t = que[top++].t;
				if (r == r0 && c == c0) continue;
				if (dist[r][c] < t) continue;
				for (i = 0; i < hi[r][c]; i++) {
					nr = tr[r][c][i], nc = tc[r][c][i];
					if (dist[nr][nc] > t+1) {
						dist[nr][nc] = t+1;
						que[end].r = nr, que[end].c = nc, que[end++].t = t+1;
					}
				}
			}
			for (i = 0; i < hi[r0][c0]; i++) {
				nr = tr[r0][c0][i], nc = tc[r0][c0][i];
				if (cost[r0][c0] > dist[nr][nc]) {
					cost[r0][c0] = dist[nr][nc];
					if (cost[r0][c0] < cost2[r0][c0]) {
						t = cost[r0][c0];
						cost[r0][c0] = cost2[r0][c0];
						cost2[r0][c0] = t;
					}
				}
			}
		}
		cost[h-1][w-1] = 0;
		printf("%d\n", calc(h-1, w-1));
	}
	return 0;
}
