Amazing Mazes

You are asked to solve maze problems. If you cannot get through these mazes, you might not get through the contest either!

A maze is a rectangular area filled with unit squares arranged in rows and columns. The area is enclosed by walls except for its entry and exit. The entry is at the leftmost part of the top side of the rectangle: the top edge of the top-left square is open. The exit is at the rightmost part of the bottom side in the same way: the bottom edge of the bottom-right square is open.

Inside the maze you may move from a square to any square that is horizontally or vertically adjacent to it. Two adjacent squares may be separated by a wall, however, and you cannot pass through a wall.

Your task is to find the length of the shortest path from the entry to the exit. There may be more than one shortest path, or there may be none.

The input consists of one or more datasets, each describing one maze.

The first line of a dataset contains two integers, the width $w$ and the height $h$ of the rectangular area, in this order.

The next $2h - 1$ lines describe whether walls separate the squares.

• The odd-numbered lines (the 1st, 3rd, … of these lines) each begin with a single space followed by $w - 1$ integers separated by spaces. The $k$-th integer says whether a wall stands between the $k$-th and $(k+1)$-th squares (counting from the left) of one row. Read from top to bottom, these lines correspond to row $1$, row $2$, …, row $h$.
• The even-numbered lines (the 2nd, 4th, …) each contain $w$ integers separated by spaces. The $k$-th integer says whether a wall stands between the $k$-th squares of two vertically adjacent rows.

An integer $1$ means a wall is present; $0$ means no wall is there.

The end of the input is indicated by a line containing two zeros.

The number of datasets is at most $100$. Both the width and the height are between $2$ and $30$, inclusive.

For each dataset, output on a single line one integer: the length of the shortest path from the entry to the exit, measured as the number of squares visited (the entry and exit squares are both counted). If there is no path through the maze, output $0$. The line must contain nothing but this number.