#include <algorithm>
#include <cstdio>
#include <functional>
#include <numeric>
#include <queue>
#include <vector>

using namespace std;

constexpr int INF = 99999999;
struct V {
    bool exist = false;
    int d = INF;
    int prev = 0;
    V() = default;
    V(bool e, int dd, int p)
        : exist{e}
        , d{dd}
        , prev{p}
    {
    }
};

int main()
{
    while (true) {
        size_t w;
        size_t h;
        scanf("%ld %ld", &w, &h);

        if (w == 0 && h == 0) {
            break;
        }

        const auto size = w * h;

        vector<vector<V>> am{size};
        for (auto&& r : am) {
            r.resize(size);
        }

        vector<pair<int, int>> es;
        for (size_t i = 0; i < 2 * h - 1; ++i) {
            if (i % 2 == 0) {
                for (size_t j = 0; j < w - 1; ++j) {
                    int t;
                    scanf("%d", &t);
                    if (t == 0) {
                        auto id = j + (i / 2) * w;
                        es.push_back(make_pair(id, id + 1));
                        am[id][id + 1] = V(true, INF, 0);
                        am[id + 1][id] = V(true, INF, 0);
                    }
                }
            }
            else {
                for (size_t j = 0; j < w; ++j) {
                    int t;
                    scanf("%d", &t);
                    if (t == 0) {
                        auto id = j + (i / 2) * w;
                        es.push_back(make_pair(id, id + w));
                        am[id][id + w] = V(true, INF, 0);
                        am[id + w][id] = V(true, INF, 0);
                    }
                }
            }
        }

        am[0][0].d = 1;
        am[0][0].exist = true;
        using TT = pair<size_t, V>;
        vector<TT> q;
        for (size_t i = 0; i < am.size(); ++i) {
            for (size_t j = 0; j < am.size(); ++j) {
                if (am[i][j].exist) {
                    q.push_back(make_pair(i, am[i][j]));
                    break;
                }
            }
        }
        while (!q.empty()) {
            auto it =
                min_element(begin(q), end(q), [](const TT& l, const TT& r) {
                    return l.second.d < r.second.d;
                });
            auto u = *it;
            q.erase(it);
            for (size_t i = 0; i < am.size(); ++i) {
                auto&& v = am[u.first][i];
                if (v.exist) {
                    auto alt = u.second.d + 1;
                    if (v.d > alt) {
                        v.d = alt;
                        for (size_t j = 0; j < q.size(); ++j) {
                            if (q[j].first == i) {
                                q[j].second.d = alt;
                            }
                        }
                    }
                }
                am[i][u.first] = v;
            }
        }
        int min = 0;
        auto it = min_element(begin(am[size - 1]), end(am[size - 1]),
                              [](const V& l, const V& r) { return l.d < r.d; });
        if (it->d != INF) {
            min = it->d;
        }

        // for (size_t i = 0; i < am.size(); ++i) {
        //    auto&& v = am[size - 1][i];
        //    if (v.exist) {
        //        if (v.d < min) {
        //            min = v.d;
        //        }
        //    }
        //}
        // if (min == INF) {
        //    min = 0;
        //}
        printf("%d\n", min);
    }
}

Measured memory_bytes: 11872