output_description: For each dataset, output a line having an integer indicating the length of the
  shortest path from the entry to the exit. The length of a path is given by the
  number of visited squares. If there exists no path to go through the maze,
  output a line containing a single zero. The line should not contain any
  character other than this number.
input_description: The input consists of one or more datasets, each of which represents a maze.
  
  The first line of a dataset contains two integer numbers, the width _w_ and
  the height _h_ of the rectangular area, in this order.
  
  The following 2 × _h_ − 1 lines of a dataset describe whether there are walls
  between squares or not. The first line starts with a space and the rest of the
  line contains _w_ − 1 integers, 1 or 0, separated by a space. These indicate
  whether walls separate horizontally adjoining squares in the first row. An
  integer 1 indicates a wall is placed, and 0 indicates no wall is there. The
  second line starts without a space and contains _w_ integers, 1 or 0,
  separated by a space. These indicate whether walls separate vertically
  adjoining squares in the first and the second rows. An integer 1/0 indicates a
  wall is placed or not. The following lines indicate placing of walls between
  horizontally and vertically adjoining squares, alternately, in the same
  manner.
  
  The end of the input is indicated by a line containing two zeros.
  
  The number of datasets is no more than 100. Both the widths and the heights of
  rectangular areas are no less than 2 and no more than 30.
attempt: from collections import deque
  
  while True:
      W, H = map(int, input().split(" "))
      if W == 0 and H == 0:
          break
  
      field = []
      for _ in range(2 * H - 1):
          row = list(input())
          if len(row) == 2 * W - 2:
              row.append(" ")
          field.append(row)
  
      gy = 2 * H - 2
      gx = 2 * W - 2
  
      queue = deque()
      queue.append((0, 0, 1))
  
      min_step = 0
      while len(queue) > 0:
          y, x, step = queue.popleft()
          if field[y][x] != " ":
              continue
          else:
              field[y][x] = "X"
  
          if y == gy and x == gx:
              min_step = step
              break
  
          for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
              if 0 <= y + dy <= gy and 0 <= x + dx <= gx:
                  if field[y + dy][x + dx] == "0":
                      queue.append((y + 2 * dy, x + 2 * dx, step + 1))
  
      print(min_step)
  
problem_description: B: Amazing Mazes
  
  You are requested to solve maze problems. Without passing through these mazes,
  you might not be able to pass through the domestic contest!
  
  A maze here is a rectangular area of a number of squares, lined up both
  lengthwise and widthwise, The area is surrounded by walls except for its entry
  and exit. The entry to the maze is at the leftmost part of the upper side of
  the rectangular area, that is, the upper side of the uppermost leftmost square
  of the maze is open. The exit is located at the rightmost part of the lower
  side, likewise.
  
  In the maze, you can move from a square to one of the squares adjoining either
  horizontally or vertically. Adjoining squares, however, may be separated by a
  wall, and when they are, you cannot go through the wall.
  
  Your task is to find the length of the shortest path from the entry to the
  exit. Note that there may be more than one shortest paths, or there may be
  none.
samples: [{"input": "![](https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_D2010_B-1)\n\n    \n    \n    2 3\n     1\n    0 1\n     0\n    1 0\n     1\n    9 4\n     1 0 1 0 0 0 0 0\n    0 1 1 0 1 1 0 0 0\n     1 0 1 1 0 0 0 0\n    0 0 0 0 0 0 0 1 1\n     0 0 0 1 0 0 1 1\n    0 0 0 0 1 1 0 0 0\n     0 0 0 0 0 0 1 0\n    12 5\n     1 0 0 0 0 0 0 0 0 0 0\n    0 0 0 1 1 0 0 0 0 0 0 0\n     1 0 1 0 0 0 0 0 0 0 0\n    0 0 0 0 0 0 1 1 0 0 0 0\n     0 0 1 0 0 1 0 1 0 0 0\n    0 0 0 1 1 0 1 1 0 1 1 0\n     0 0 0 0 0 1 0 0 1 0 0\n    0 0 0 0 0 0 0 0 0 0 0 0\n     0 0 0 0 0 0 0 0 1 0 0\n    0 0", "output": "0\n    20"}]