#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;
    int id = 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);
                    }
                }
            }
        }
        // for (auto&& i : es) {
        //    printf("%d, %d\n", i.first, i.second);
        //}
        am[0][0].d = 1;
        am[0][0].exist = true;
        using TT = pair<int, V>;
        function<bool(const TT&, const TT&)> comp =
            [](const TT& l, const TT& r) { return l.second.d < r.second.d; };

        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()) {
            // printf("l\n");
            // for (auto&& i : q) {
            //    printf("%d %d\n", i.first, i.second.d);
            //}
            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;
                            }
                        }
                        // for (auto j = 0; j < q.size(); ++j) {
                        //    if (q[j].first == i) {
                        //        q[j].second.d = alt;
                        //    }
                        //}
                    }
                }
                am[i][u.first] = v;
                // printf("a%d %d\n", i, u.first);
            }
            // for (auto&& r : am) {
            //    for (auto&& l : r) {
            //        printf("%d ", l.d);
            //    }
            //    putchar('\n');
            //}
        }
        int min = INF;
        for (size_t i = 0; i < am.size(); ++i) {
            auto&& v = am[size - 1][i];
            // printf("%d\n", v.d);
            if (v.exist) {
                if (v.d < min) {
                    min = v.d;
                }
            }
        }
        if (min == INF) {
            min = 0;
        }
        printf("%d\n", min);
    }
}

Measured memory_bytes: 14988