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):
while True:
    w, h = map(int, input().split())
    if w == 0: break
    goal = (w,h)
    vart = []
    hori = []
    for i in range(2*h-1):
        if i % 2 == 0:
            vart.append(list(map(int, input().split())))
        else:
            hori.append(list(map(int, input().split())))
    node = [[0 for i in range(h)] for i in range(w)]
    queue = [(0,0)]
    while queue:
        p = queue.pop(0)
        x, y = p[0], p[1]
        node[x][y] += 1
        if y-1 >= 0 and hori[y-1][x] == 0 and node[x][y-1] == 0:
            node[x][y-1] = node[x][y]
            queue.append((x,y-1))
        if y+1 < h and hori[y][x] == 0 and node[x][y+1] == 0:
            node[x][y+1] = node[x][y]
            queue.append((x,y+1))
        if x-1 >= 0 and vart[y][x-1] == 0 and node[x-1][y] == 0:
            node[x-1][y] = node[x][y]
            queue.append((x-1,y))
        if x+1 < w and vart[y][x] == 0 and node[x+1][y] == 0:
            node[x+1][y] = node[x][y]
            queue.append((x+1,y))
    print(node[w-1][h-1])

Solution (Python):
while True:
    w, h = map(int, input().split())
    if w == 0: break
    goal = (w,h)
    vart = []
    hori = []
    for i in range(2*h-1):
        if i % 2 == 0:
            vart.append(list(map(int, input().split())))
        else:
            hori.append(list(map(int, input().split())))
    node = [[0 for i in range(h)] for i in range(w)]
    queue = [(0,0,1)]
    while queue:
        p = queue.pop(0)
        x, y, z = p[0], p[1], p[2]
        node[x][y] += 1
        if y-1 >= 0 and hori[y-1][x] == 0 and node[x][y-1] == 0:
            node[x][y-1] = node[x][y]
            queue.append((x,y-1,z+1))
        if y+1 < h and hori[y][x] == 0 and node[x][y+1] == 0:
            node[x][y+1] = node[x][y]
            queue.append((x,y+1,z+1))
        if x-1 >= 0 and vart[y][x-1] == 0 and node[x-1][y] == 0:
            node[x-1][y] = node[x][y]
            queue.append((x-1,y,z+1))
        if x+1 < w and vart[y][x] == 0 and node[x+1][y] == 0:
            node[x+1][y] = node[x][y]
            queue.append((x+1,y,z+1))
    print(node[w-1][h-1])

Solution (Python):
while True:
    w, h = map(int, input().split())
    if w == 0: break
    goal = (w,h)
    vart = []
    hori = []
    for i in range(2*h-1):
        if i % 2 == 0:
            vart.append(list(map(int, input().split())))
        else:
            hori.append(list(map(int, input().split())))
    node = [[0 for i in range(h)] for i in range(w)]
    queue = [(0,0,1)]
    while queue:
        p = queue.pop(0)
        x, y, z = p[0], p[1], p[2]
        node[x][y] += 1
        if y-1 >= 0 and hori[y-1][x] == 0 and node[x][y-1] == 0:
            node[x][y-1] = node[x][y]
            queue.append((x,y-1,z+1))
        if y+1 < h and hori[y][x] == 0 and node[x][y+1] == 0:
            node[x][y+1] = node[x][y]
            queue.append((x,y+1,z+1))
        if x-1 >= 0 and vart[y][x-1] == 0 and node[x-1][y] == 0:
            node[x-1][y] = node[x][y]
            queue.append((x-1,y,z+1))
        if x+1 < w and vart[y][x] == 0 and node[x+1][y] == 0:
            node[x+1][y] = node[x][y]
            queue.append((x+1,y,z+1))
    print(node[w-1][h-1])

Solution (Python):
while True:
    w, h = map(int, input().split())
    if w == 0 and h ==0:
        break
    goal = (w,h)
    vart = []
    hori = []
    for i in range(2*h-1):
        if i % 2 == 0:
            vart.append(list(map(int, input().split())))
        else:
            hori.append(list(map(int, input().split())))
    node = [[0 for i in range(h)] for i in range(w)]
    queue = [(0,0,1)]
    res = 0
    while queue:
        p = queue.pop(0)
        x, y, z = p[0], p[1], p[2]
        if x == w-1 and y == h-1:
            res = z
            break
        node[x][y] += 1
        if y-1 >= 0 and hori[y-1][x] == 0 and node[x][y-1] == 0:
            node[x][y-1] = node[x][y]
            queue.append((x,y-1,z+1))
        if y+1 < h and hori[y][x] == 0 and node[x][y+1] == 0:
            node[x][y+1] = node[x][y]
            queue.append((x,y+1,z+1))
        if x-1 >= 0 and vart[y][x-1] == 0 and node[x-1][y] == 0:
            node[x-1][y] = node[x][y]
            queue.append((x-1,y,z+1))
        if x+1 < w and vart[y][x] == 0 and node[x+1][y] == 0:
            node[x+1][y] = node[x][y]
            queue.append((x+1,y,z+1))
    print(res)

Solution (Python):
while True:
    w, h = map(int, input().split())
    vart = []
    hori = []
    if w == 0 and h ==0:
        break
    for i in range(2*h-1):
        if i % 2 == 0:
            vart.append(list(map(int, input().split())))
        else:
            hori.append(list(map(int, input().split())))
    node = [[0 for i in range(h)] for i in range(w)]
    queue = [(0,0,1)]
    res = 0
    while queue:
        p = queue.pop(0)
        x, y, z = p[0], p[1], p[2]
        if x == w-1 and y == h-1:
            res = z
            break
        node[x][y] += 1
        if y-1 >= 0 and hori[y-1][x] == 0 and node[x][y-1] == 0:
            node[x][y-1] = node[x][y]
            queue.append((x,y-1,z+1))
        if y+1 < h and hori[y][x] == 0 and node[x][y+1] == 0:
            node[x][y+1] = node[x][y]
            queue.append((x,y+1,z+1))
        if x-1 >= 0 and vart[y][x-1] == 0 and node[x-1][y] == 0:
            node[x-1][y] = node[x][y]
            queue.append((x-1,y,z+1))
        if x+1 < w and vart[y][x] == 0 and node[x+1][y] == 0:
            node[x+1][y] = node[x][y]
            queue.append((x+1,y,z+1))
    print(res)

Solution (Python):
while True:
    m,n = map(int,input().split())
    sw = []
    bw = []
    if m == 0 and n == 0:
        break
    for i in range(2*n-1):
        if i % 2 == 0:
            sw.append(list(map(int,input().split())))
        else:
            bw.append(list(map(int,input().split())))
    flag = [[0 for i in range(m)] for j in range(n)]
    l = [(0,0,1)]
    res = 0
    while l:
        bf = l.pop(0)
        x,y,z = bf[0],bf[1],bf[2]
        if x == n-1 and y == m-1:
            res = z
            break
        if 1 <= x and bw[x-1][y] == 0 and flag[x-1][y] == 0:
            flag[x-1][y] = 1
            l.append((x-1,y,z+1))
        if y < m-1 and sw[x][y] == 0 and flag[x][y+1] == 0:
            flag[x][y+1] = 1
            l.append((x,y+1,z+1))
        if 1 <= y and sw[x][y-1] == 0 and flag[x][y-1] == 0:
            flag[x][y-1] = 1
            l.append((x,y-1,z+1))
        if x < n-1 and bw[x][y] == 0 and flag[x+1][y] == 0:
            flag[x+1][y] = 1
            l.append((x+1,y,z+1))
    print(res)

Solution (Python):
while True:
    m,n = map(int,input().split())
    sw = []
    bw = []
    if m == 0 and n == 0:
        break
    for i in range(2*n-1):
        if i % 2 == 0:
            sw.append(list(map(int,input().split())))
        else:
            bw.append(list(map(int,input().split())))
    flag = [[0 for i in range(m)] for j in range(n)]
    l = [(0,0,1)]
    res = 0
    while l:
        bf = l.pop(0)
        if bf[0] == n-1 and bf[1] == m-1:
            res = bf[2]
            break
        flag[bf[0]][bf[1]] = 1
        if 1 <= bf[0] and bw[bf[0]-1][bf[1]] == 0 and flag[bf[0]-1][bf[1]] == 0:
            flag[bf[0]-1][bf[1]] = 1
            l.append((bf[0]-1,bf[1],bf[2]+1))
        if bf[1] < m-1 and sw[bf[0]][bf[1]] == 0 and flag[bf[0]][bf[1]+1] == 0:
            flag[bf[0]][bf[1]+1] = 1
            l.append((bf[0],bf[1]+1,bf[2]+1))
        if 1 <= bf[1] and sw[bf[0]][bf[1]-1] == 0 and flag[bf[0]][bf[1]-1] == 0:
            flag[bf[0]][bf[1]-1] = 1
            l.append((bf[0],bf[1]-1,bf[2]+1))
        if bf[0] < n-1 and bw[bf[0]][bf[1]] == 0 and flag[bf[0]+1][bf[1]] == 0:
            flag[bf[0]+1][bf[1]] = 1
            l.append((bf[0]+1,bf[1],bf[2]+1))
    print(res)

Solution (Python):
while True:
    w, h = map(int, input().split())
    if w == 0:
        break
    tatekabe = []
    yokokabe = []
    for _ in range(h-1):
        tatekabe.append(list(map(int, input().split())))
        yokokabe.append(list(map(int, input().split())))
    tatekabe.append(list(map(int, input().split())))

    field = [[1e10 for i in range(w)] for j in range(h)]
    
    x, y = 0, 0
    field[y][x] = 1
    stack = [[x, y]]
    while True:
        if stack == []:
            break
        x, y = stack.pop()
        c = field[y][x]
        if x != w-1 and tatekabe[y][x] == 0 and c+1 < field[y][x+1]:
            field[y][x+1] = c + 1
            stack.append([x+1, y])
        if x != 0 and tatekabe[y][x-1] == 0 and c+1 < field[y][x-1]:
            field[y][x-1] = c + 1
            stack.append([x-1, y])
        if y != h-1 and yokokabe[y][x] == 0 and c+1 < field[y+1][x]:
            field[y+1][x] = c + 1
            stack.append([x, y+1])
        if y != 0 and yokokabe[y-1][x] == 0 and c+1 < field[y-1][x]:
            field[y-1][x] = c + 1
            stack.append([x, y-1])
    if field[h-1][w-1] == 1e10:
        print(0)
    else:
        print(field[h-1][w-1])

Solution (Python):
from collections import deque

while True:
    a,b = map(int,input().split())
    if a == b == 0:
        break
    map_list = []
    map_list.append([1 for i in range(2 * a + 1)])
    for i in range(2 * b - 1):
        
        lis_c = list(map(int,input().split()))
        if i % 2 == 0:
            row = [2 for i in range(2 * a - 1)]
            for j in range(len(lis_c)):
                row[2 * j + 1] = lis_c[j]
            
        else:
            row = [1 for i in range(2 * a - 1)]
            for j in range(len(lis_c)):
                row[2 * j] = lis_c[j]
        row.append(1)
        row.insert(0,1)
        map_list.append(row)
    map_list.append([1 for i in range(2 * a + 1)])


    
    time = 0
    M_dic = {}
    M_que = deque([])
    M_que.append([time,[1,1]])
    M_dic[(1,1)] = time
    while True:
        now_list = M_que.popleft()
        now_time = now_list[0]

        now_pos = now_list[1]
        if now_pos == [2 * b - 1,2 * a - 1]:
            print(now_time + 1)
            break
            
        if map_list[now_pos[0] + 1][now_pos[1]] == 0:
            if not (now_pos[0] + 2,now_pos[1]) in M_dic:
                M_dic[(now_pos[0] + 2,now_pos[1])] = now_time + 1
                M_que.append([now_time + 1, [now_pos[0] + 2,now_pos[1]]])
   
        if map_list[now_pos[0]][now_pos[1] + 1] == 0:
            if not (now_pos[0],now_pos[1] + 2) in M_dic:
                M_dic[(now_pos[0],now_pos[1] + 2)] = now_time + 1
                M_que.append([now_time + 1, [now_pos[0],now_pos[1] + 2]])
                
        if map_list[now_pos[0] - 1][now_pos[1]] == 0:
            if not (now_pos[0] - 2,now_pos[1]) in M_dic:
                M_dic[(now_pos[0] - 2,now_pos[1])] = now_time + 1
                M_que.append([now_time + 1, [now_pos[0] - 2,now_pos[1]]])
   
        if map_list[now_pos[0]][now_pos[1] - 1] == 0:
            if not (now_pos[0],now_pos[1] - 2) in M_dic:
                M_dic[(now_pos[0],now_pos[1] - 2)] = now_time + 1
                M_que.append([now_time + 1, [now_pos[0],now_pos[1] - 2]])
                
        if len(M_que) == 0:
            print(0)
            break

Solution (Python):
d = [[0, -1],
     [0, 1],
     [-1, 0],
     [1, 0]]

INF = 1000000

tile = {"0":0,
        "1":1,
        " ":2}

def idx(i):
    return 2*i

output = []
while True:
    w, h = input().split()
    w = int(w)
    h = int(h)

    if w == 0:
        break

    maze = [[2 for i in range(2*w-1)] for j in range(2*h-1)]
    l = [[INF for i in range(w)] for j in range(h)]
    for j in range(2*h-1):
        row = input()
        for i in range(len(row)):
            maze[j][i] = tile[row[i]]
    
    queue = [(0, 0, 1)]
    while queue:
        x, y, count = queue.pop(0)

        for ud, rl in d:
            xxt = idx(x)+ud
            yyt = idx(y)+rl
            if xxt>=0 and xxt<w*2-1 and yyt>=0 and yyt<h*2-1:
                if maze[yyt][xxt] == 0:
                    xt = x+ud
                    yt = y+rl
                    if l[yt][xt] > count+1:
                        l[yt][xt] = count+1
                        queue.append((xt, yt, count+1))

    if l[h-1][w-1] == INF:
        output.append(0)
    else:
        output.append(l[h-1][w-1])

for i in output:
    print(i)

Solution (Python):


from collections import deque
INF = 1000000
dij = [[1, 0, -1, 0], [0, 1, 0, -1]]

def vectorBool(i, j, k, maze):
    if k == 0 and maze[2*i+1][j] == 1:
        return False
    elif k == 1 and maze[2*i][j] == 1:
        return False
    elif k == 2 and maze[2*i-1][j] == 1:
        return False
    elif k == 3 and maze[2*i][j-1] == 1:
        return False
    else:
        return True


def bfs(w, h, maze):
    q = deque()
    dist = [[INF for i in range(w)]for j in range(h)]
    q.append((0, 0))
    dist[0][0] = 1

    while(len(q)):
        p = q.popleft()
        if p == (h - 1, w - 1):
            break
        for k in range(4):
            nxy = (p[0] + dij[0][k], p[1] + dij[1][k])
            if(0<= nxy[0] < h) and (0<= nxy[1] < w) and vectorBool(p[0], p[1], k, maze) and dist[nxy[0]][nxy[1]] == INF:
                q.append(nxy)
                dist[nxy[0]][nxy[1]] = dist[p[0]][p[1]] + 1
    if dist[h-1][w-1] == INF:
        return 0
    else:
        return dist[h-1][w-1]


while True:
    w, h = list(map(int, input().split()))
    if w == 0 and h ==0:
        break
    maze = []
    for i in range(2 * h - 1):
        maze.append(list(map(int, input().split())))
    print(bfs(w, h, maze))

Solution (Python):

"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1166&lang=jp

"""
import sys
from sys import stdin
from collections import deque
input = stdin.readline


def bfs(maze, w, h):
    
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]

    
    sx = 0                   
    sy = 0
    gx = w - 1                   
    gy = h - 1

    d = [[float('inf')] * w for _ in range(h)] 
    Q = deque()
    Q.append((sx, sy))
    d[sy][sx] = 0
    while Q:
        cx, cy = Q.popleft()        
        if cx == gx and cy == gy:
            return d[gy][gx] + 1
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            
            if is_passable(maze, w, h, cx, cy, dx[i], dy[i]) and d[ny][nx] == float('inf'):
                Q.append((nx, ny))
                d[ny][nx] = d[cy][cx] + 1
    return 0


def is_passable(maze, w, h, cx, cy, dx, dy):
    if not 0 <= (cx + dx) < w:
        return False
    if not 0 <= (cy + dy) < h:
        return False
    if dy == -1:                
        return True if maze[cy*2-1][cx] == 0 else False
    if dy == 1:                 
        return True if maze[cy*2+1][cx] == 0 else False
    if dx == -1:                
        return True if maze[cy*2][cx-1] == 0 else False
    if dx == 1:                 
        return True if maze[cy*2][cx] == 0 else False


def solve(maze, w, h):
    return bfs(maze, w, h)


def main(args):
    while True:
        w, h = map(int, input().split(' '))
        if w == 0 and h == 0:
            break

        maze = []
        for d in range(h*2-1):
            maze.append([int(x) for x in input().strip().split(' ')])

        res = solve(maze, w, h)
        print(res)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):

"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1166&lang=jp
AC
"""
import sys
from sys import stdin
from collections import deque
input = stdin.readline


def bfs(maze, w, h):
    
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]

    
    sx = 0                   
    sy = 0
    gx = w - 1               
    gy = h - 1

    d = [[float('inf')] * w for _ in range(h)] 
    Q = deque()
    Q.append((sx, sy))
    d[sy][sx] = 0
    while Q:
        cx, cy = Q.popleft()        
        if cx == gx and cy == gy:
            return d[gy][gx] + 1    
        for i in range(len(dx)):
            nx = cx + dx[i]
            ny = cy + dy[i]
            
            if is_passable(maze, w, h, cx, cy, dx[i], dy[i]) and d[ny][nx] == float('inf'):
                Q.append((nx, ny))
                d[ny][nx] = d[cy][cx] + 1
    return 0                    


def is_passable(maze, w, h, cx, cy, dx, dy):
    
    if not 0 <= (cx + dx) < w:
        return False
    if not 0 <= (cy + dy) < h:
        return False
    if dy == -1:                
        return True if maze[cy*2-1][cx] == 0 else False
    if dy == 1:                 
        return True if maze[cy*2+1][cx] == 0 else False
    if dx == -1:                
        return True if maze[cy*2][cx-1] == 0 else False
    if dx == 1:                 
        return True if maze[cy*2][cx] == 0 else False


def solve(maze, w, h):
    return bfs(maze, w, h)


def main(args):
    while True:
        w, h = map(int, input().split(' '))
        if w == 0 and h == 0:
            break

        maze = []
        for d in range(h*2-1):
            maze.append([int(x) for x in input().strip().split(' ')])

        res = solve(maze, w, h)
        print(res)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):
from collections import deque
while True:
    W,H = map(int, input().split())
    if W == 0: break
    es = [[] for i in range(W*H)]
    for y in range(H):
        walls_h = list(map(int, input().split()))
        for x in range(W-1):
            if walls_h[x]: continue
            es[y*W + x].append(y*W + x+1)
            es[y*W + x+1].append(y*W + x)
        if y == H-1: break
        walls_v = list(map(int, input().split()))
        for x in range(W):
            if walls_v[x]: continue
            es[y*W + x].append((y+1)*W + x)
            es[(y+1)*W + x].append(y*W + x)
    q = deque([0])
    dist = [0] * (W*H)
    dist[0] = 1
    while q:
        fr = q.popleft()
        for to in es[fr]:
            if dist[to] == 0:
                dist[to] = dist[fr] + 1
                q.append(to)
    print(dist[-1])

Solution (Python):
def solve():
    import sys
    file_input = sys.stdin
    
    while True:
        w, h = map(int, file_input.readline().split())
        if w == 0 and h == 0:
            break
        
        width = 2 * w + 1
        
        maze = '1' * width
        line = file_input.readline()
        maze += '1' + line.rstrip() + ' 1'
        for _ in range(h - 1):
            line = file_input.readline()
            maze += '1' + line.rstrip() + '1'
            line = file_input.readline()
            maze += '1' + line.rstrip() + ' 1'
        maze += '1' * width
        
        start = width + 1
        goal = len(maze) - width - 2
        
        from collections import deque
        forward_q = deque()
        forward_q.append(start)
        reverse_q = deque()
        reverse_q.append(goal)
        
        forward_rec = [None] * (goal + 1)
        forward_rec[start] = 1
        reverse_rec = [None] * (goal + 1)
        reverse_rec[goal] = 1
        
        adj_move = (1, -1, width, -width)
        
        def shortest_path_len():
            while forward_q and reverse_q:
                fp = forward_q.popleft()
                fp_len = forward_rec[fp]
                rp = reverse_q.popleft()
                rp_len = reverse_rec[rp]
                
                for move in adj_move:
                    wall = maze[fp + move]
                    if wall == '0':
                        next_place = fp + move * 2
                        if forward_rec[next_place] == None:
                            if reverse_rec[next_place]:
                                return fp_len + reverse_rec[next_place]
                            forward_q.append(next_place)
                            forward_rec[next_place] = fp_len + 1
                    wall = maze[rp + move]
                    if wall == '0':
                        next_place = rp + move * 2
                        if reverse_rec[next_place] == None:
                            if forward_rec[next_place]:
                                return rp_len + forward_rec[next_place]
                            reverse_q.append(next_place)
                            reverse_rec[next_place] = rp_len + 1
            return 0
        
        print(shortest_path_len())

solve()

Solution (Python):
def solve():
    import sys
    file_input = sys.stdin
    
    while True:
        w, h = map(int, file_input.readline().split())
        if w == 0 and h == 0:
            break
        
        width = 2 * w + 1
        
        maze = '1' * width
        line = file_input.readline()
        maze += '1' + line.rstrip() + ' 1'
        for _ in range(h - 1):
            line = file_input.readline()
            maze += '1' + line.rstrip() + '1'
            line = file_input.readline()
            maze += '1' + line.rstrip() + ' 1'
        maze += '1' * width
        
        start = width + 1
        goal = len(maze) - width - 2
        
        from collections import deque
        forward_q = deque()
        forward_q.append(start)
        reverse_q = deque()
        reverse_q.append(goal)
        
        forward_rec = [None] * (goal + 1)
        forward_rec[start] = 1
        reverse_rec = [None] * (goal + 1)
        reverse_rec[goal] = 1
        
        adj_move = (1, -1, width, -width)
        
        while forward_q and reverse_q:
            fp = forward_q.popleft()
            fp_len = forward_rec[fp]
            rp = reverse_q.popleft()
            rp_len = reverse_rec[rp]
            
            for move in adj_move:
                wall = maze[fp + move]
                if wall == '0':
                    next_place = fp + move * 2
                    if forward_rec[next_place] == None:
                        if reverse_rec[next_place]:
                            print(fp_len + reverse_rec[next_place])
                            break
                        forward_q.append(next_place)
                        forward_rec[next_place] = fp_len + 1
                wall = maze[rp + move]
                if wall == '0':
                    next_place = rp + move * 2
                    if reverse_rec[next_place] == None:
                        if forward_rec[next_place]:
                            print(rp_len + forward_rec[next_place])
                            break
                        reverse_q.append(next_place)
                        reverse_rec[next_place] = rp_len + 1
            else:
                continue
            break
        else:
            print(0)

solve()

Solution (Python):
from queue import Queue

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

    vl = list()
    hl = list()
    for i in range(h * 2 - 1):
        if i % 2:
            hl.append(list(map(int, input().split())))
        else:
            vl.append(list(map(int, input().split())))

    q = Queue()
    d = [[w * h + 1 for i in range(h)] for j in range(w)]
    q.put((0, 0))
    d[0][0] = 1
    while not q.empty():
        x, y = q.get()

        if x > 0 and (not vl[y][x - 1]) and d[x - 1][y] > h * w:
            d[x - 1][y] = d[x][y] + 1
            q.put((x - 1, y))

        if x < w - 1 and (not vl[y][x]) and d[x + 1][y] > h * w:
            d[x + 1][y] = d[x][y] + 1
            q.put((x + 1, y))

        if y > 0 and (not hl[y - 1][x]) and d[x][y - 1] > h * w:
            d[x][y - 1] = d[x][y] + 1
            q.put((x, y - 1))

        if y < h - 1 and (not hl[y][x]) and d[x][y + 1] > h * w:
            d[x][y + 1] = d[x][y] + 1
            q.put((x, y + 1))
    
    if d[w - 1][h - 1] > h * w:
        print(0)
    else:
        print(d[w - 1][h - 1])

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d):
        self.e[u].append([v,d])
        self.e[v].append([u,d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def search(self, s, t):
        d = collections.defaultdict(lambda: inf)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            if u == t:
                return d[t]
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return None

def main():
    rr = []

    while True:
        w,h = LI()
        if h == 0 and w == 0:
            break

        a = [LI() for _ in range(h*2-1)]

        dk = Dijkstra()
        for i in range(h):
            for j in range(w-1):
                if a[i*2][j] == 0:
                    dk.add((i,j), (i,j+1), 1)
        for i in range(h-1):
            for j in range(w):
                if a[i*2+1][j] == 0:
                    dk.add((i,j), (i+1,j), 1)
        r = dk.search((0,0),(h-1,w-1))
        if r:
            rr.append(r+1)
        else:
            rr.append(0)

    return '\n'.join(map(str, rr))


print(main())

Solution (Python):
from Queue import Queue
mv=((1,0),(-1,0),(0,1),(0,-1))
while True:
    w,h=map(int,raw_input().split())
    if w==h==0:break
    INF=1e3
    dist=[[INF]*w for i in range(h)]
    L=[raw_input() for i in range(2*h-1)]
    Q=Queue()
    Q.put((0,0,1))
    dist[0][0]=1
    while not Q.empty():
        x,y,d=Q.get()
        for dx,dy in mv:
            mx=x+dx
            my=y+dy
            if mx<0 or w<=mx or my<0 or h<=my:
                continue
            if dist[my][mx]>d+1 and L[y*2+dy][x*2+dx]=="0":
                dist[my][mx]=d+1
                Q.put((mx,my,d+1))
    print dist[h-1][w-1] if dist[h-1][w-1]!=INF else 0

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

while True:
    W,H = map(int, input().split())
    if W == 0 and H == 0:
        break
    
    wallcolumn = [None]*H
    wallrow = [[1]*W] + [None]*(H-1) + [[1]*W]
    for h in range(H):
        wallcolumn[h] = [1] + list(map(int, input().split())) + [1]
        if h < H-1:
            wallrow[h+1] = list(map(int, input().split()))
    
    distancemat = [[-1]*W for _ in range(H)]
    queue = deque()
    queue.append((0,0))
    distancemat[0][0] = 1
    
    while queue:
        x,y = queue.popleft()
        distance = distancemat[y][x]
        
        if x > 0:
            if wallcolumn[y][x] == 0 and distancemat[y][x-1] == -1:
                distancemat[y][x-1] = distance + 1
                queue.append((x-1,y))
        
        if x < W-1:
            if wallcolumn[y][x+1] == 0 and distancemat[y][x+1] == -1:
                distancemat[y][x+1] = distance + 1
                queue.append((x+1,y))
        
        if y > 0:
            if wallrow[y][x] == 0 and distancemat[y-1][x] == -1:
                queue.append((x,y-1))
                distancemat[y-1][x] = distance + 1
        
        if y < H-1:
            if wallrow[y+1][x] == 0 and distancemat[y+1][x] == -1:
                queue.append((x,y+1))
                distancemat[y+1][x] = distance + 1
    
    if distancemat[H-1][W-1] == -1:
        print(0)
    else:
        print(distancemat[H-1][W-1])