import scala.annotation.tailrec
import scala.collection.mutable

object Main extends App {
  import scala.io.StdIn._
  solve
  @tailrec def solve: Unit = {
    val Array(w, h) = readLine.trim.split(' ').map(_.toInt)
    if (w == 0) return
    val maze = new Maze(h, w)
    for (i ← 0 until (2 * h - 1)){
      val line = readLine.trim.stripPrefix(" ").split(' ').map(_.toInt)
      if (i % 2 == 0){
        line.zipWithIndex.foreach{case (isBlocked, pos) ⇒ if (isBlocked == 1) maze.addWallVertical(i / 2, pos)}
      }else {
        line.zipWithIndex.foreach{case (isBlocked, pos) ⇒ if (isBlocked == 1) maze.addWallHorizontal(i / 2, pos)}
      }
    }
    val queue: mutable.PriorityQueue[(Cell, Int)] = mutable.PriorityQueue[(Cell, Int)]()(Ordering.by[(Cell, Int), Int]{case (_, d) ⇒ d}.reverse).also{p ⇒ p.enqueue((Cell(0, 0), 1))}
    val memo = Array.tabulate(h){_ ⇒ Array.tabulate(w){_ ⇒ Int.MaxValue}}.also{m ⇒ m(0)(0) = 1}
    val goal = Cell(w - 1, h - 1)
    while (queue.nonEmpty && queue.head._1 != goal) {
      val (current, distance) = queue.dequeue()
      if (memo(current.y)(current.x) == distance){
        for (neighbor ← maze.neighbors(current)) {
          if (memo(neighbor.y)(neighbor.x) > distance + 1){
            memo(neighbor.y)(neighbor.x) = distance + 1
            queue.enqueue((neighbor, distance + 1))
          }
        }
      }
    }
    println(
      if (queue.isEmpty) 0 else queue.head._2
    )
    solve
  }

  object Maze{
    private val relationNeighbor: List[Cell] = List(Cell(0, -1), Cell(-1, 0), Cell(0, 1), Cell(1, 0))
    private def selectNeighbor(selector: Int, list: List[Cell]): List[Cell] = {
      list match{
        case Nil ⇒ Nil
        case h::t if selector % 2 == 1 ⇒ h::selectNeighbor(selector / 2, t)
        case _::t ⇒ selectNeighbor(selector / 2, t)
      }
    }
  }
  class Maze(val height: Int, val width: Int) {
    private val mState: Array[Array[Int]] = Array.tabulate(height){_ ⇒ Array.tabulate(width){_ ⇒ 15}}//右下左上
    def addWallVertical(row: Int, position: Int): Unit = {
      mState(row)(position) &= 7
      mState(row)(position + 1) &= 13
    }
    def addWallHorizontal(row: Int, position: Int): Unit = {
      mState(row)(position) &= 11
      mState(row + 1)(position) &= 14
    }
    def neighbors(cell: Cell): List[Cell] = Maze.selectNeighbor(mState(cell.y)(cell.x), Maze.relationNeighbor.map(_ + cell)).filter(this.isContain)
    private def isContain(cell: Cell): Boolean = (0 until height).contains(cell.y) && (0 until width).contains(cell.x)
  }
  case class Cell(x: Int, y: Int) {
    def +(that: Cell): Cell = Cell(x + that.x, y + that.y)
  }
  implicit class ScopeFunc[T](private val value: T) {
    def let[A](func:T ⇒ A): A = func(value)
    def also(func:T ⇒ Unit): T = {
      func(value)
      value
    }
  }
}
