Amazing Mazes (AOJ 1166) by ynu_b
Contest: 3472    RunID: 2316309    Status: Accepted    Date: Sun May 14 17:52:12 JST 2017


#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, s, n) for(int i = s; i < n; ++i)
#define rep(i, n)		 REP(i, 0, n)
#define SORT(c)			 sort((c).begin(), (c).end())
#define IINF	INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false
 
typedef long long				ll;
typedef pair <int, int> ii;
 
/*
struct point{
	ll x;
	ll y;
	point(){x = 0;y = 0;}
	point(ll x, ll y):x(x), y(y){}
};
*/

int dw[] = {0, 1, 0 ,-1};
int dh[] = {1, 0 ,-1, 0};
//下右上左

int main() {

	int w, h;
	while(cin >> w >> h, w, h){
		vector<vector<int>> yoko(h ,vector<int>(w+1, 1));
		vector<vector<int>> tate(h+1 ,vector<int>(w, 1));
		
		rep(i, 2*h-1){
			if(i%2==0){
				rep(j, w-1) cin >> yoko[(int)(i/2)][j+1];
			}
			else{
				rep(j, w) cin >> tate[(int)(i/2)+1][j];
			}
		}
		
		/*
		rep(i, yoko.size()){
			rep(j, yoko[i].size()) cout << yoko[i][j]<<"\t";
			cout << endl;
		}
		cout << endl;
		rep(i, tate.size()){
			rep(j, tate[i].size()) cout << tate[i][j]<<"\t";
			cout << endl;
		}
		*/
		
		queue<pair<ii, int>> qu;
		qu.push(make_pair(make_pair(0, 0), 0)); // h, w
		
		vector<vector<bool>> used(h, vector<bool>(w));
		
		int ans = 0;
		
		while(!qu.empty()){
			pair<ii, int> tmp = qu.front();
			qu.pop();
			
			int hh = tmp.first.first;
			int ww = tmp.first.second;
			
			if(used[hh][ww]) continue;
			used[hh][ww] = true;
			if(hh == h-1 && ww == w-1){
				ans = tmp.second + 1;
				break;
			}
			
			if(yoko[hh][ww] == 0) qu.push(make_pair(make_pair(hh, ww-1), tmp.second + 1));
			if(yoko[hh][ww+1] == 0) qu.push(make_pair(make_pair(hh, ww+1), tmp.second + 1));
			if(tate[hh][ww] == 0) qu.push(make_pair(make_pair(hh-1, ww), tmp.second + 1));
			if(tate[hh+1][ww] == 0) qu.push(make_pair(make_pair(hh+1, ww), tmp.second + 1));
		}
		
		cout << ans << endl;

	}

	return 0;
}