Problem:
Problem 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. Input 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. Output 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. Sample Input 2 3
 1
0 1
 0
1 0
 1
9 4
 1 0 1 0 0 0 0 0
0 1 1 0 1 1 0 0 0
 1 0 1 1 0 0 0 0
0 0 0 0 0 0 0 1 1
 0 0 0 1 0 0 1 1
0 0 0 0 1 1 0 0 0
 0 0 0 0 0 0 1 0
12 5
 1 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0 0 0
 1 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 0 0 0
 0 0 1 0 0 1 0 1 0 0 0
0 0 0 1 1 0 1 1 0 1 1 0
 0 0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 1 0 0
0 0 Output for the Sample Input 4
0
20

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)
from collections import deque


def bfs(scores, right_bars, bottom_bars, start_point, goal_point):
    queue = deque([start_point])
    while queue:
        now_point = queue.popleft()
        mv = [[-1, 0], [0, -1], [1, 0], [0, 1]]
        if now_point[0] == 0:
            
            mv.remove([-1, 0])
        if now_point[0] >= h - 1:
            
            mv.remove([1, 0])
        if now_point[1] == 0:
            
            mv.remove([0, -1])
        if now_point[1] >= w - 1:
            
            mv.remove([0, 1])
        for next_position in mv:
            next_point = [now_point[0] + next_position[0],
                          now_point[1] + next_position[1]]
            if next_position == [-1, 0]:  
                if bottom_bars[next_point[0]][next_point[1]] == 0 and scores[now_point[0]][now_point[1]] + 1 < scores[next_point[0]][next_point[1]]:
                    queue.append(next_point)
                    scores[next_point[0]][next_point[1]
                                          ] = scores[now_point[0]][now_point[1]] + 1
            if next_position == [0, -1]:  
                if right_bars[next_point[0]][next_point[1]] == 0 and scores[now_point[0]][now_point[1]] + 1 < scores[next_point[0]][next_point[1]]:
                    queue.append(next_point)
                    scores[next_point[0]][next_point[1]
                                          ] = scores[now_point[0]][now_point[1]] + 1
            if next_position == [1, 0]:  
                
                
                
                
                
                if bottom_bars[now_point[0]][now_point[1]] == 0 and scores[now_point[0]][now_point[1]] + 1 < scores[next_point[0]][next_point[1]]:
                    queue.append(next_point)
                    scores[next_point[0]][next_point[1]
                                          ] = scores[now_point[0]][now_point[1]] + 1
            if next_position == [0, 1]:  
                if right_bars[now_point[0]][now_point[1]] == 0 and scores[now_point[0]][now_point[1]] + 1 < scores[next_point[0]][next_point[1]]:
                    queue.append(next_point)
                    scores[next_point[0]][next_point[1]
                                          ] = scores[now_point[0]][now_point[1]] + 1
    
    if scores[goal_point[0]][goal_point[1]] == (len(scores[0]) * len(scores)):
        return 0
    return scores[goal_point[0]][goal_point[1]]


costs = []
while True:
    w, h = map(int, input().split())
    if [w, h] == [0, 0]:
        break
    scores = [[w * h for _ in range(w)] for _ in range(h)]
    scores[0][0] = 1
    right_bars = []
    bottom_bars = []
    for _ in range(h - 1):
        right_bar = list(map(int, input().split()))
        bottom_bar = list(map(int, input().split()))
        right_bars.append(right_bar)
        bottom_bars.append(bottom_bar)
    right_bar = list(map(int, input().split()))
    right_bars.append(right_bar)
    start_point = [0, 0]
    goal_point = [h - 1, w - 1]
    cost = bfs(scores, right_bars, bottom_bars, start_point, goal_point)
    costs.append(cost)
for cost in costs:
    print(cost)

Solution (Python):
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()
closed = [0, 0, 0, 0]
sys.setrecursionlimit(10 ** 8)

while True:
    w, h = map(int, input().split())
    if w == h == 0:
        break
    info = [[closed for _ in range(w + 2)]]  
    for _ in range(h):
        info.append([closed] + [[1] * 4 for _ in range(w)] + [closed])
    info.append([closed for _ in range(w + 2)])
    for i in range(1, w + 1):  
        info[0][i][0] = 0
        info[-1][i][2] = 0
    for i in range(1, h + 1):
        info[i][0][1] = 0
        info[i][-1][3] = 0
    for i in range(1, h + 1):
        vertical_wall = list(map(int, input().split()))
        for j in range(1, w):
            if vertical_wall[j-1] == 1:
                info[i][j][3] = 0
                info[i][j + 1][1] = 0
        if i < h:
            horizontally_wall = list(map(int, input().split()))
            for j in range(1, w + 1):
                if horizontally_wall[j-1] == 1:
                    info[i][j][2] = 0
                    info[i + 1][j][0] = 0
    stack = deque([[1, 1, 1]])
    info[1][1] = closed
    while len(stack) > 0:
        y, x, dis = stack.popleft()
        if y == h and x == w:
            print(dis)
            break
        if info[y][x + 1][1] == 1:
            info[y][x + 1] = closed
            stack.append([y, x + 1, dis + 1])
        if info[y][x - 1][3] == 1:
            info[y][x - 1] = closed
            stack.append([y, x - 1, dis + 1])
        if info[y + 1][x][0] == 1:
            info[y + 1][x] = closed
            stack.append([y + 1, x, dis + 1])
        if info[y - 1][x][2] == 1:
            info[y - 1][x] = closed
            stack.append([y - 1, x, dis + 1])
        if len(stack) == 0:
            print(0)
            break

Solution (Python):
from collections import deque

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

while True:
    w, h = map(int, input().split())

    if w == 0:
        exit()

    wall = [list(map(int, input().split())) for _ in range(2 * h - 1)]

    d = [[0]*w for _ in range(h)]
    d[0][0] = 1

    q = deque()
    q.append((0, 0))

    while q:
        sy, sx = q.popleft()
        for i in range(4):
            ty = sy + dy[i]
            tx = sx + dx[i]
            if 0<=tx<w and 0<=ty<h and d[ty][tx] == 0 and wall[sy + ty][(sx + tx) // 2] != 1:
                d[ty][tx] = d[sy][sx] + 1
                q.append((ty, tx))

    print(d[-1][-1])

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

d = [(1,0),(-1,0),(0,1),(0,-1)]
def solve(h,w):
    s = LIR(2*h-1)
    bfs = [[0]*w for i in range(h)]
    bfs[0][0] = 1
    q = deque([(0,0)])
    g = (h-1,w-1)
    while q:
        y,x = q.popleft()
        if (y,x) == g:
            print(bfs[y][x])
            return
        nb = bfs[y][x]+1
        for dy,dx in d:
            ny,nx = y+dy,x+dx
            if 0 <= ny < h and 0 <= nx < w:
                if dy and not s[2*min(y,ny)+1][nx]:
                    if not bfs[ny][nx]:
                        bfs[ny][nx] = nb
                        q.append((ny,nx))
                elif dx and not s[2*ny][min(x,nx)]:
                    if not bfs[ny][nx]:
                        bfs[ny][nx] = nb
                        q.append((ny,nx))
    print(0)
    return


if __name__ == "__main__":
    while 1:
        w,h = LI()
        if w == h == 0:
            break
        solve(h,w)

Solution (Python):
def main():
    import queue
    import sys
    input=sys.stdin.readline
    
    while True:
        w,h=map(int,input().split())
        if w==0 and h==0:
            break
        maze=[list(map(int,input().split())) for _ in range(2*h-1)]
    

        q=queue.Queue()
        dist=[[-1]*w for _ in range(h)]
        dist[0][0]=1
        q.put((0,0))
        while q.qsize()!=0:
            p=q.get()
            ny=p[0]
            nx=p[1]

            y=ny
            x=nx+1
            if  x<w and dist[y][x]==-1 and maze[2*y][nx]==0:
                dist[y][x]=dist[ny][nx]+1
                q.put((y,x))
            
            y=ny
            x=nx-1
            if x>=0 and dist[y][x]==-1 and maze[2*y][x]==0:
                dist[y][x]=dist[ny][nx]+1
                q.put((y,x))
        
            y=ny+1
            x=nx
            if y<h and dist[y][x]==-1 and maze[2*ny+1][x]==0:
                dist[y][x]=dist[ny][nx]+1
                q.put((y,x))
        
            y=ny-1
            x=nx
            if y>=0 and dist[y][x]==-1 and maze[2*ny-1][x]==0:
                dist[y][x]=dist[ny][nx]+1
                q.put((y,x))
        
        if dist[-1][-1]==-1:
            print(0)
        else:
            print(dist[-1][-1])

if __name__=='__main__':
    main()

Solution (Python):
import sys
import queue
input = sys.stdin.readline

while True:
    w,h = map(int,input().split())
    if w == 0 and h == 0:
        break
    h_wall =[]
    v_wall =[]
    for i in range(h):
        h_wall.append(list(map(int,input().split())))
        if i < h-1 :
            v_wall.append(list(map(int,input().split())))
    maze = [[0 for _ in range(w)] for _ in range(h)]

    q = queue.Queue()
    q.put((0,0))
    maze[0][0] = 1
    while not q.empty():
        y, x = q.get()
        for dx, dy in ((1,0),(0,1),(-1,0),(0,-1)):
            ny = y + dy
            nx = x + dx
            if 0 <= ny < h and 0 <= nx < w:
                if dx == 0 and v_wall[min(y,ny)][x] == 1:
                    continue
                if dy == 0 and h_wall[y][min(x,nx)] == 1:
                    continue
                if maze[ny][nx] == 0:
                    maze[ny][nx] = maze[y][x] + 1
                    q.put((ny,nx))
    print (maze[h-1][w-1])

Solution (Python):
class Room:
    def __init__(self, row, col, ROWS, COLS):
        self.row = row
        self.col = col
        self.dist = None
        self.top = True if row > 0 else False
        self.left = True if col > 0 else False
        self.right = True if col < COLS - 1 else False
        self.bot = True if row < ROWS - 1 else False

if __name__ == '__main__':
    while True:
        COLS, ROWS = list(map(int, input().strip().split()))
        if ROWS == 0 and COLS == 0:
            break

        maze = [ [ Room(row, col, ROWS, COLS) for col in range(COLS) ] for row in range(ROWS) ]

        row = 0
        while True:
            walls = list(map(int, input().strip().split()))
            for col in range(COLS - 1):
                if walls[col] == 1:
                    maze[row][col].right = False
                    maze[row][col + 1].left = False
            
            if row == ROWS - 1:
                break
            
            walls = list(map(int, input().strip().split()))
            for col in range(COLS):
                if walls[col] == 1:
                    maze[row][col].bot = False
                    maze[row + 1][col].top = False

            row += 1

        maze[0][0].dist = 1
        processList = [ (0,0) ]
        while len(processList) > 0:
            row, col = processList.pop(0)
            room = maze[row][col]

            if room.top:
                rr = row - 1
                cc = col
                adjRoom = maze[rr][cc]
                if adjRoom.dist == None:
                    adjRoom.dist = room.dist + 1
                    processList.append((rr, cc))

            if room.bot:
                rr = row + 1
                cc = col
                adjRoom = maze[rr][cc]
                if adjRoom.dist == None:
                    adjRoom.dist = room.dist + 1
                    processList.append((rr, cc))

            if room.left:
                rr = row
                cc = col - 1
                adjRoom = maze[rr][cc]
                if adjRoom.dist == None:
                    adjRoom.dist = room.dist + 1
                    processList.append((rr, cc))

            if room.right:
                rr = row
                cc = col + 1
                adjRoom = maze[rr][cc]
                if adjRoom.dist == None:
                    adjRoom.dist = room.dist + 1
                    processList.append((rr, cc))

        dist = maze[ROWS - 1][COLS - 1].dist
        print(dist if dist != None else 0)

Solution (Python):
import queue

def bfs(w, h, maze):
    dx = [-1, 0, 0, 1]
    dy = [0, 1, -1, 0]
    dist = [ [-1] * (w+1) for _ in range(h+1) ]
    q = queue.Queue()
    q.put([0, 0, 0])
    dist[0][0] = 0

    while not q.empty():
        x, y, d = q.get()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]

            if maze[y][x][i] == 0: continue
            if dist[ny][nx] != -1: continue
            
            q.put( [nx, ny, d+1] )
            dist[ny][nx] = d+1

    return dist[h-1][w-1] + 1

while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0: break
    maze = [ [[0] * 4 for x in range(w+1)] for _ in range(h+1) ]

    for i in range(h*2-1):
        if i & 1:
            t = [ int(x) for x in input().split() ]
            for j, tt in enumerate(t):
                if tt == 0:
                    maze[i//2][j][1] = 1
                    maze[i//2+1][j][2] = 1
        else:
            t = [ int(x) for x in input().split() ]
            for j, tt in enumerate(t):
                if tt == 0:
                    maze[i//2][j][3] = 1
                    maze[i//2][j+1][0] = 1
    print(bfs(w, h, maze))

Solution (Python):
from collections import deque
INF = 10 ** 10

def search(nowi, nowj, next, root, yoko, tate):
    global INF
    if nowi == h - 1 and nowj == w - 1:
        return root[nowi][nowj]
    
    dis = root[nowi][nowj]
    if 0 < nowi:
        if root[nowi - 1][nowj] == INF and tate[nowi - 1][nowj] == 0:
            next.append([nowi - 1, nowj])
            root[nowi - 1][nowj] = dis + 1
    if 0 < nowj:
        if root[nowi][nowj - 1] == INF and yoko[nowi][nowj - 1] == 0:
            next.append([nowi, nowj - 1])
            root[nowi][nowj - 1] = dis + 1
    if nowi < len(root) - 1:
        if root[nowi + 1][nowj] == INF and tate[nowi][nowj] == 0:
            next.append([nowi + 1, nowj])
            root[nowi + 1][nowj] = dis + 1 
    if nowj < len(root[nowi]) - 1:
        if root[nowi][nowj + 1] == INF and yoko[nowi][nowj] == 0:
            next.append([nowi, nowj + 1])
            root[nowi][nowj + 1] = dis + 1
    if len(next) == 0:
        return 0
    nextij = next.popleft()
    nexti = nextij[0]
    nextj = nextij[1]
    return search(nexti, nextj, next, root, yoko, tate)


while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0:
        break
    yoko = []
    tate = []

    for i in range(2 * h - 1):
        if i % 2 == 0:
            yoko.append(list(map(int, input().split())))
        else:
            tate.append(list(map(int, input().split())))
    
    root = [[INF for _ in range(w)] for _ in range(h)]
    root[0][0] = 1
    next = deque()
    print(search(0, 0, next, root, yoko, tate))

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

def calc(y,x):
    return y*W+x


def dijkstra(lines,N,s):
    weight = [INF]*N
    weight[s] = 0

    def search(s,w_0,q,weight):
        for t,w in lines[s]:
            w += w_0
            if weight[t] > w:
                heapq.heappush(q,[w,t])
                weight[t] = w

    q = [[0,s]]
    heapq.heapify(q)
    while q:
        w,n = heapq.heappop(q)
        search(n,w,q,weight)

    return weight



while True:
    W,H = inpl()
    if W==0 and H == 0:
        break
    else:
        lines = defaultdict(set)
        for i in range(2*H-1):
            if i%2 == 0:
                h = i//2
                ww = inpl()
                for i,w in enumerate(ww):
                    if w == 0:
                        lines[calc(h,i)].add((calc(h,i+1),1))
                        lines[calc(h,i+1)].add((calc(h,i),1))
            else:
                h = i//2
                ww = inpl()
                for i,w in enumerate(ww):
                    if w == 0:
                        lines[calc(h,i)].add((calc(h+1,i),1))
                        lines[calc(h+1,i)].add((calc(h,i),1))

        weight = dijkstra(lines,H*W,0)
        if weight[-1] == INF:
            print(0)
        else:
            print(weight[-1]+1)

Solution (Python):
from collections import deque

def solve(W, H, walls):
    edge = [[[] for i in range(W)] for j in range(H)]
    for i in range(H):
        for j in range(W-1):
            if (not walls[2*i][j]):
                edge[i][j].append((i, j+1))
                edge[i][j+1].append((i,j))
    for i in range(H-1):
        for j in range(W):
            if (not walls[2*i+1][j]):
                edge[i][j].append((i+1, j))
                edge[i+1][j].append((i,j))

    q = deque()
    q.append((0, 0))
    dist = [[-1]*W for i in range(H)]
    dist[0][0] = 1

    while q:
        y, x = q.popleft()
        for ny, nx in edge[y][x]:
            if (dist[ny][nx] == -1):
                dist[ny][nx] = dist[y][x] + 1
                q.append((ny, nx))


    return dist[H-1][W-1] if (dist[H-1][W-1] != -1) else 0

"""
def solve(W, H, walls):
    dire = [(1,0), (0,1), (-1,0), (0,-1)]
    field = [[1]*(2*W) for i in range(2*H)]
    for i in range(0,2*H,2):
        vertical_wall = walls[i]
        for j in range(W-1):
            if (vertical_wall[j]):
                field[i][j*2+1] = field[i+1][j*2+1] = 0

    for i in range(1,2*H-1,2):
        horizontal_wall = walls[i]
        for j in range(W):
            if (horizontal_wall[j]):
                field[i][j*2] = field[i][j*2+1] = 0

    q = deque()
    dist = [[-1]*(2*W) for i in range(2*H)]
    q.append((0,0))
    dist[0][0] = 0

    while q:
        y, x = q.popleft()
        for dy, dx in dire:
            if (y+dy<2*H) and (y+dy>=0) and (x+dx<2*W) and (x+dx>=0):
                if (field[y+dy][x+dx]) and (dist[y+dy][x+dx] == -1):
                    dist[y+dy][x+dx] = dist[y][x] + 1
                    q.append((y+dy, x+dx))
    res = dist[2*H-1][2*W-1]//2

    for i in field:
        for j in i:
            print("." if j else "
        print()

    ans_dist = [[0]*W for i in range(H)]
    for i in range(H):
        for j in range(W):
            ans_dist[i][j] = max(dist[2*i][2*j], dist[2*i][2*j+1], dist[2*i+1][2*j], dist[2*i+1][2*j+1]) // 2
    for i in ans_dist:
        print(i)

    
       

    return res if (res != -1) else 0

"""
def main():
    ans = []
    while True:
        W, H = map(int, input().split())
        if (W==0) and (H==0):
            break
        walls = [list(map(int, input().split())) for i in range(2*H-1)]
        ans.append(solve(W, H, walls))
    
    for i in ans:
        print(i)

main()

Solution (Python):
while(True):
  A, B = map(int, input().split())
  if (A == 0 and B ==0):
    break
  vert = []
  hori = []

  hist = {}

  for i in range(B - 1):
    vert.append(list(map(int, input().split())))
    hori.append(list(map(int, input().split())))

  vert.append(list(map(int, input().split())))

  next_pos = [{"x": 0, "y": 0, "step": 0}]
  hist['0::0'] = 0
  while(True):
    if (len(next_pos) == 0):
      pos = {}
      pos["step"] = 0
      break
    pos = next_pos.pop(0)
    
    if (pos["x"] == A - 1 and pos["y"] == B - 1):
      pos["step"] += 1
      break

    
    if (f'{pos["x"] + 1}::{pos["y"]}' not in hist and pos["x"] < A - 1 and pos["y"] < B and vert[pos["y"]][pos["x"]] == 0):
      next_pos.append({"x": pos["x"] + 1, "y": pos["y"], "step": pos["step"] + 1})
      hist[f'{pos["x"] + 1}::{pos["y"]}'] = 0

    
    if (f'{pos["x"]}::{pos["y"] + 1}' not in hist and pos["x"] < A and pos["y"] < B - 1 and hori[pos["y"]][pos["x"]] == 0):
      next_pos.append({"x": pos["x"], "y": pos["y"] + 1, "step": pos["step"] + 1})
      hist[f'{pos["x"]}::{pos["y"] + 1}'] = 0

    
    if (f'{pos["x"] - 1}::{pos["y"]}' not in hist and pos["x"] - 1 >= 0 and pos["y"] < B and vert[pos["y"]][pos["x"] - 1] == 0):
      next_pos.append({"x": pos["x"] - 1, "y": pos["y"], "step": pos["step"] + 1})
      hist[f'{pos["x"] - 1}::{pos["y"]}'] = 0

    
    if (f'{pos["x"]}::{pos["y"] - 1}' not in hist and pos["x"] < A and pos["y"] - 1 >= 0 and hori[pos["y"] - 1][pos["x"]] == 0):
      next_pos.append({"x": pos["x"], "y": pos["y"] - 1, "step": pos["step"] + 1})
      hist[f'{pos["x"]}::{pos["y"] - 1}'] = 0

  print(pos["step"])

Solution (Python):

from queue import Queue

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

while True:
    w, h = map(int, input().split())
    if w == 0:
        exit()
    wall = [list(map(int, input().split())) for _ in range(2 * h - 1)]

    d = [[0] * w for _ in range(h)]
    d[0][0] = 1

    q = Queue()
    q.put((0, 0))
    while not q.empty():
        sy, sx = q.get()
        for i in range(4):
            ty = sy + dy[i]
            tx = sx + dx[i]
            if tx < 0 or w - 1 < tx or ty < 0 or h - 1 < ty:
                continue
            if d[ty][tx] > 0:
                continue
            if wall[sy + ty][(sx + tx) // 2] == 1:
                continue

            d[ty][tx] = d[sy][sx] + 1
            q.put((ty, tx))

    print(d[-1][-1])

Solution (Python):
while True:
    w, h = map(int, input().split())
    if w == 0:
        break
    row = []
    col = []
    for i in range(h-1):
        row.append(input().split())
        col.append(input().split())
    row.append(input().split())
    check_map = [[False for i in range(w)] for j in range(h)]
    search_list = [[0, 0, 1]]
    check_map[0][0] = True
    ok = False
    while len(search_list) > 0:
        x, y, step = search_list.pop(0)
        if x == w-1 and y == h-1:
            print(step)
            ok = True
            break
        
        if x > 0:
            if row[y][x-1] == "0" and not check_map[y][x-1]:
                search_list.append([x-1, y, step+1])
                check_map[y][x-1] = True
        
        if x < w-1:
            if row[y][x] == "0" and not check_map[y][x+1]:
                search_list.append([x+1, y, step+1])
                check_map[y][x+1] = True
        
        if y > 0:
            if col[y-1][x] == "0" and not check_map[y-1][x]:
                search_list.append([x, y-1, step+1])
                check_map[y-1][x] = True
        
        if y < h-1:
            if col[y][x] == "0" and not check_map[y+1][x]:
                search_list.append([x, y+1, step+1])
                check_map[y+1][x] = True
    if not ok:
        print(0)

Solution (Python):


from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

def B():
    
    ANS = []
    move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    while True:
        
        w, h = LI()
        if w == h == 0:
            break
        
        
        field = SR(2 * h - 1)
        
        check = [[True] * (2 * w - 1) for i in range(2 * h - 1)]
        
        next = deque()
        
        next.append((0, 0))
        ans = 1
        flg = True

        while next and flg:
            now = next
            next = deque()
            while now:
                x, y = now.pop()
                for mx, my in move:
                    nx, ny = x + mx, y + my

                    if 0 <= nx < 2 * w - 1 and 0 <= ny < 2 * h - 1 and field[ny][nx] == '0' and check[ny+my][nx+mx]:
                            next.append((nx + mx, ny + my))
                            check[ny + my][nx + mx] = False
                            if nx+mx == 2 * w - 2 and ny+my == 2 * h - 2:
                                ANS.append(ans+1)
                                flg = False
                                next = deque()
                                now = deque()
                                break
            ans += 1
        if flg:
            ANS.append(0)


    return ANS

if __name__ == '__main__':
    A = B()
    for i in range(len(A)):
        print(A[i])

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    while True:
        n = II()
        if not n:
            break
        a = IR(n)
        a.sort()
        print(sum(a[1:-1])//(n-2))
            
    return


def B():
    move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    while True:
        w, h = LI()
        if w == h == 0:
            break
        field = SR(2 * h - 1)
        check = [[True] * (2 * w - 1) for i in range(2 * h - 1)]
        next = deque()
        next.append((0, 0))
        ans = 1
        flg = True
        
        while next and flg:
            now = next
            next = deque()
            while now:
                x, y = now.pop()
                for mx, my in move:
                    mmx, mmy = x + mx, y + my
                    
                    if 0 <= mmx < 2 * w - 1 and 0 <= mmy < 2 * h - 1:
                        if field[mmy][mmx] == '0' and check[mmy+my][mmx+mx]:
                            next.append((mmx + mx, mmy + my))
                            check[mmy + my][mmx + mx] = False
                            if mmx+mx == 2 * w - 2 and mmy+my == 2 * h - 2:
                                print(ans+1)
                                flg = False
                                next = deque()
                                now = deque()
                                break
            ans += 1
        if flg:
            print(0)
            
    
    return


def C():
    return


def D():
    return


def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == '__main__':
    B()

Solution (Python):

from collections import deque

while True:
    w, h = map(int, input().split())
    if w == 0:
        break
    lr_walls = []
    ud_walls = []
    for i in range(2 * h - 1):
        wall = list(map(int, input().split()))
        if i % 2 == 0:
            lr_walls.append(wall)
        else:
            ud_walls.append(wall)
    checked = [[False] * w for _ in range(h)]
    checked[0][0] = True
    que = deque()
    que.append((1, 0, 0))
    while que:
        score, x, y = que.popleft()
        if (x, y) == (w - 1, h - 1):
            print(score)
            break

        if x < w - 1 and lr_walls[y][x] == 0 and not checked[y][x + 1]:
            checked[y][x + 1] = True
            que.append((score + 1, x + 1, y))

        if x > 0 and lr_walls[y][x - 1] == 0 and not checked[y][x - 1]:
            checked[y][x - 1] = True
            que.append((score + 1, x - 1, y))

        if y < h - 1 and ud_walls[y][x] == 0 and not checked[y + 1][x]:
            checked[y + 1][x] = True
            que.append((score + 1, x, y + 1))

        if y > 0 and ud_walls[y - 1][x] == 0 and not checked[y - 1][x]:
            checked[y - 1][x] = True
            que.append((score + 1, x, y - 1))
    else:
        print(0)