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):
from copy import deepcopy
while True:
    w, h = map(int, input().split())
    if w == 0:
        break
    wwal = []  
    hwal = []  
    a = [0] * w
    b = []
    for i in range(2 * h - 1):
        if i % 2 == 0:
            wwal.append(list(map(int, input().split())))
            c = deepcopy(a)
            b.append(c)
        else:
            hwal.append(list(map(int, input().split())))
    b[0][0] = 1
    start = [[0, 0]]
    flag = 0
    while flag == 0:
        flag = 1
        stamemo = []
        for i in range(len(start)):
            t = start.pop()
            
            if t[1] != 0:
                if wwal[t[0]][t[1] - 1] == 0 and b[t[0]][t[1]-1] == 0:
                    b[t[0]][t[1] - 1] = b[t[0]][t[1]] + 1
                    stamemo.append([t[0], t[1] - 1])
                    flag = 0
            
            if t[1] != w-1:
                if wwal[t[0]][t[1]] == 0 and b[t[0]][t[1]+1] == 0:
                    b[t[0]][t[1] + 1] = b[t[0]][t[1]] + 1
                    if t[0] == h - 1 and t[1] + 1 == w - 1:
                        print(b[t[0]][t[1] + 1])
                        flag = 2
                        break
                    stamemo.append([t[0], t[1]+1])
                    flag = 0
            
            if t[0] != 0:
                if hwal[t[0] - 1][t[1]] == 0 and b[t[0] - 1][t[1]] == 0:
                    b[t[0] - 1][t[1]] = b[t[0]][t[1]] + 1
                    stamemo.append([t[0] - 1, t[1]])
                    flag = 0
            
            if t[0] != h-1:
                if hwal[t[0]][t[1]] == 0 and b[t[0] + 1][t[1]] == 0:
                    b[t[0] + 1][t[1]] = b[t[0]][t[1]] + 1
                    if t[0]+1 == h - 1 and t[1] == w - 1:
                        print(b[t[0]+1][t[1]])
                        flag = 2
                        break
                    stamemo.append([t[0] + 1, t[1]])
                    flag = 0
        start = stamemo
    if flag == 1:
        print(0)

Solution (Python):

import queue

while True:
    tmp = input().split(" ")
    w = int(tmp[0])
    h = int(tmp[1])
    if w == 0:
        break

    yoko_wall = []
    tate_wall = []

    for i in range(2*h-1):
        if i%2 == 0:
            omega = []
            for k in input().split(" ")[1:]:
                omega.append(int(k))
            yoko_wall.append(omega)
            
        else:
            omega2 = []
            for r in input().split(" "):
                omega2.append(int(r))
            tate_wall.append(omega2)

    
    
    
    

    map_count = []
    for i in range(h):
        tmp = []
        for j in range(w):
            tmp.append(1000)
        map_count.append(tmp)

    q = queue.Queue()
    q.put([0,0])
    map_count[0][0] = 0

    
    while True:
        if q.empty():
            print("0")
            break

        start = q.get()

        if start[0] == h-1 and start[1] == w-1:
            print(str(map_count[h-1][w-1]+1))
            break

        
        ue = [start[0]-1,start[1]]
        sita = [start[0]+1,start[1]]
        migi = [start[0],start[1]+1]
        hidari = [start[0],start[1]-1]

        

        if ue[0] >= 0 and ue[0] < h and ue[1] >= 0 and ue[1] < w:
            
            
            
            if tate_wall[ue[0]][ue[1]] == 0:
                if map_count[ue[0]][ue[1]] == 1000:
                    map_count[ue[0]][ue[1]] = map_count[start[0]][start[1]] + 1
                    q.put(ue)
                    
                
                    

        if sita[0] >= 0 and sita[0] < h and sita[1] >= 0 and sita[1] < w:
            
            
            
            if tate_wall[start[0]][start[1]] == 0:
                
                if map_count[sita[0]][sita[1]] == 1000:
                    
                    map_count[sita[0]][sita[1]] = map_count[start[0]][start[1]] + 1
                    q.put(sita)
                    


        if migi[0] >= 0 and migi[0] < h and migi[1] >= 0 and migi[1] < w:
            
            
            
            if yoko_wall[start[0]][start[1]] == 0:
                if map_count[migi[0]][migi[1]] == 1000:
                    map_count[migi[0]][migi[1]] = map_count[start[0]][start[1]] + 1
                    q.put(migi)
                    
        
            

        if hidari[0] >= 0 and hidari[0] < h and hidari[1] >= 0 and hidari[1] < w:
            
            
            
            if yoko_wall[hidari[0]][hidari[1]] == 0:
                if map_count[hidari[0]][hidari[1]] == 1000:
                    map_count[hidari[0]][hidari[1]] = map_count[start[0]][start[1]] + 1
                    q.put(hidari)

Solution (Python):

import queue

while True:
    tmp = input().split(" ")
    w = int(tmp[0])
    h = int(tmp[1])
    if w == 0:
        break

    yoko_wall = []
    tate_wall = []

    for i in range(2*h-1):
        if i%2 == 0:
            omega = []
            for k in input().split(" ")[1:]:
                omega.append(int(k))
            yoko_wall.append(omega)
            
        else:
            omega2 = []
            for r in input().split(" "):
                omega2.append(int(r))
            tate_wall.append(omega2)

    map_count = []
    for i in range(h):
        tmp = []
        for j in range(w):
            tmp.append(1000)
        map_count.append(tmp)

    q = queue.Queue()
    q.put([0,0])
    map_count[0][0] = 0

    while True:
        if q.empty():
            print("0")
            break

        start = q.get()

        if start[0] == h-1 and start[1] == w-1:
            print(str(map_count[h-1][w-1]+1))
            break

        ue = [start[0]-1,start[1]]
        sita = [start[0]+1,start[1]]
        migi = [start[0],start[1]+1]
        hidari = [start[0],start[1]-1]


        if ue[0] >= 0 and ue[0] < h and ue[1] >= 0 and ue[1] < w:
            if tate_wall[ue[0]][ue[1]] == 0:
                if map_count[ue[0]][ue[1]] == 1000:
                    map_count[ue[0]][ue[1]] = map_count[start[0]][start[1]] + 1
                    q.put(ue)

        if sita[0] >= 0 and sita[0] < h and sita[1] >= 0 and sita[1] < w:
            if tate_wall[start[0]][start[1]] == 0:
                if map_count[sita[0]][sita[1]] == 1000:
                    map_count[sita[0]][sita[1]] = map_count[start[0]][start[1]] + 1
                    q.put(sita)


        if migi[0] >= 0 and migi[0] < h and migi[1] >= 0 and migi[1] < w:
            if yoko_wall[start[0]][start[1]] == 0:
                if map_count[migi[0]][migi[1]] == 1000:
                    map_count[migi[0]][migi[1]] = map_count[start[0]][start[1]] + 1
                    q.put(migi)

        if hidari[0] >= 0 and hidari[0] < h and hidari[1] >= 0 and hidari[1] < w:
            if yoko_wall[hidari[0]][hidari[1]] == 0:
                if map_count[hidari[0]][hidari[1]] == 1000:
                    map_count[hidari[0]][hidari[1]] = map_count[start[0]][start[1]] + 1
                    q.put(hidari)

Solution (Python):
from collections import deque
while True:
    tmp = input().split(" ")
    w = int(tmp[0])
    h = int(tmp[1])
    if w == 0:
        break

    yoko_wall = []
    tate_wall = []

    for i in range(2*h-1):
        if i%2 == 0:
            omega = []
            for k in input().split(" ")[1:]:
                omega.append(int(k))
            yoko_wall.append(omega)
            
        else:
            omega2 = []
            for r in input().split(" "):
                omega2.append(int(r))
            tate_wall.append(omega2)

    
    
    
    

    map_count = []
    for i in range(h):
        tmp = []
        for j in range(w):
            tmp.append(1000)
        map_count.append(tmp)

    q = deque([])
    q.append([0,0])
    map_count[0][0] = 0

    
    while True:
        if len(q) == 0:
            print("0")
            break

        start = q.popleft()

        if start[0] == h-1 and start[1] == w-1:
            print(str(map_count[h-1][w-1]+1))
            break

        
        ue = [start[0]-1,start[1]]
        sita = [start[0]+1,start[1]]
        migi = [start[0],start[1]+1]
        hidari = [start[0],start[1]-1]

        

        if ue[0] >= 0 and ue[0] < h and ue[1] >= 0 and ue[1] < w:
            
            
            
            if tate_wall[ue[0]][ue[1]] == 0:
                if map_count[ue[0]][ue[1]] == 1000:
                    map_count[ue[0]][ue[1]] = map_count[start[0]][start[1]] + 1
                    q.append(ue)
                    
                
                    

        if sita[0] >= 0 and sita[0] < h and sita[1] >= 0 and sita[1] < w:
            
            
            
            if tate_wall[start[0]][start[1]] == 0:
                
                if map_count[sita[0]][sita[1]] == 1000:
                    
                    map_count[sita[0]][sita[1]] = map_count[start[0]][start[1]] + 1
                    q.append(sita)
                    


        if migi[0] >= 0 and migi[0] < h and migi[1] >= 0 and migi[1] < w:
            
            
            
            if yoko_wall[start[0]][start[1]] == 0:
                if map_count[migi[0]][migi[1]] == 1000:
                    map_count[migi[0]][migi[1]] = map_count[start[0]][start[1]] + 1
                    q.append(migi)
                    
        
            

        if hidari[0] >= 0 and hidari[0] < h and hidari[1] >= 0 and hidari[1] < w:
            
            
            
            if yoko_wall[hidari[0]][hidari[1]] == 0:
                if map_count[hidari[0]][hidari[1]] == 1000:
                    map_count[hidari[0]][hidari[1]] = map_count[start[0]][start[1]] + 1
                    q.append(hidari)

Solution (Python):
X = [1,-1,0,0]
Y = [0,0,1,-1]
B = [1,2,4,8]

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

    _map = [[0 for i in range(w)] for i in range(h)]
    dp = [[99999999 for i in range(w)] for i in range(h)]

    for i in range(h*2-1):
        for j,v in enumerate(list(map(int,input().split()))):
            if v == 0:continue
            if i % 2 == 0 :
                _map[i // 2][j] += B[0]
                if j+1 < w:
                    _map[i // 2][j+1] += B[1]
            else:
                _map[i // 2][j] += B[2]
                if (i // 2) + 1 < h:
                    _map[(i // 2)+1][j] += B[3]
    lst = [(1,0,0)]
    dp[0][0] = 1
    res = 0

    
    while len(lst) > 0:
        spam = lst.pop(0)
        for i in range(4):
            x = spam[2] + X[i]
            y = spam[1] + Y[i]
            if x < 0 or y < 0 or x >= w or y >= h or  \
                B[i] & _map[spam[1]][spam[2]] != 0 or dp[y][x] <= spam[0] + 1:
                continue
            if x+1 == w and y+1 == h:
                res = spam[0] + 1
                break
            lst.append((spam[0] + 1, y, x))
            dp[y][x] = spam[0] + 1
        if res > 0:break
        lst.sort()

    print(res)

Solution (Python):



import os
import sys
import itertools
import math
from collections import Counter, defaultdict

class Main(object):
    
    def __init__(self):
        pass

    def solve(self):
        '''
        insert your code
        '''
        while True:
            w, h = map(int, raw_input().split())
            if w == h == 0:
                break
            can_move = [[[False, False, False, False] for j in xrange(w)] for i in xrange(h)]
            for i in range(h):
                if i != 0:
                    hol = map(int, raw_input().split())
                    for j in range(w):
                        if hol[j] == 1:
                            can_move[i-1][j][3] = False
                            if i <= h - 1:
                                can_move[i][j][1] = False
                        else:
                            can_move[i-1][j][3] = True
                            if i <= h - 1:
                                can_move[i][j][1] = True
                ver = map(int, raw_input().split())
                for j in range(w-1):
                    if ver[j] == 1:
                        can_move[i][j][0] = False
                        can_move[i][j+1][2] = False
                    else:
                        can_move[i][j][0] = True
                        can_move[i][j+1][2] = True
            

            q = [(0, 0, 1)]
            d = [(0, 1), (-1, 0), (0, -1), (1, 0)]
            visited = set([(0, 0)])
            while q:
                y, x, dist = q.pop(0)
                
                if (y, x) == (h - 1, w - 1):
                    print dist
                    break
                else:
                    for i, (dy, dx) in enumerate(d):
                        if 0 <= y + dy < h and 0 <= x + dx < w and can_move[y][x][i] and (y + dy, x + dx) not in visited:
                            q.append((y + dy, x + dx, dist + 1))
                            visited.add((y + dy, x + dx))
            else:
                print 0
        return None

if __name__ == '__main__':
    m = Main()
    m.solve()

Solution (Python):
from heapq import heappop as hpop, heappush as hpush
def da (s, t, L, n):
	PreV = [None for i in range(n+1)]
	D = [float("inf") for i in range(n+1)]
	Q = list()
	PreV[s] = (0,0)
	D[s] = 0
	hpush(Q, (0,s))
	lenQ = 1
	while lenQ > 0:
		tmp = hpop(Q)
		lenQ -= 1
		for v in L[tmp[1]] :
			tmpd = tmp[0] + v[0]
			if tmpd < D[v[1]]:
				D[v[1]] = tmpd
				hpush(Q, (tmpd, v[1]))
				PreV[v[1]] = (tmpd, tmp[1])
				lenQ += 1
	return PreV

while 1:
	w,h = map(int,raw_input().split())
	if (w,h) == (0,0):
		break
	L = [[] for i in range(w*h)]
	for j in range(h * 2 - 1):
		wall = map(int,raw_input().split())
		if j % 2 == 0:
			for i in range(w-1):
				if wall[i] == 0:
					L[i+w*j/2].append((1,i+w*j/2+1))
					L[i+w*j/2+1].append((1,i+w*j/2))
		else :
			for i in range(w):
				if wall[i] == 0:
					L[i+w*(j-1)/2].append((1,i+w*(j-1)/2+w))
					L[i+w*(j-1)/2+w].append((1,i+w*(j-1)/2))
	route = da(0, w*h-1, L, w*h)
	print 0 if route[w*h-1] is None else route[w*h-1][0]+1

Solution (Python):



from heapq import heappop,heappush

def bfs(sx,sy,W,H):
    queue = []
    heappush(queue,(0,sx,sy))
    dxdy = [(0,1),(0,-1),(1,0),(-1,0)]
    visited = [[ 10**8 for i in range(W)] for j in range(H)]

    while queue != []:
        count,x,y = heappop(queue)
        if visited[y][x] != 10**8:
            continue
        visited[y][x] = count
        for nx,ny in dxdy:
            if 0 <= x + nx < W and 0 <= y + ny < H:
                if visited[y + ny][x + nx] == 10**8:
                    nextValue = Maze[y + ny][x + nx]
                    if ((nx,ny) == (1,0) and nextValue & 1 > 0) or ((nx,ny) == (0,1) and nextValue & 2 > 0) or ((nx,ny) == (-1,0) and Maze[y][x] & 1 > 0) or ((nx,ny) == (0,-1) and Maze[y][x] & 2 > 0 ):
                        continue
                    else:
                        heappush(queue,(count + 1,x+nx,y+ny))
    return visited

while True:
    w,h = map(int,input().split(" "))
    if h == 0 and w == 0:
        break
    Maze = [[0 for j in range(w)] for i in range(h)]
    for i in range(h-1):
        row = list(map(int,input().split()))
        for j in range(len(row)):
            if row[j] == 1:
                Maze[i][j+1] += 1
        col = list(map(int,input().split()))
        for j in range(len(col)):
            if col[j] == 1:
                Maze[i+1][j] += 2
    else:
        i += 1
        row = list(map(int,input().split()))
        for j in range(len(row)):
            if row[j] == 1:
                Maze[i][j+1] += 1

    ret = bfs(0,0,w,h)[h-1][w-1]
    print(ret + 1 if ret != 10**8 else 0)

Solution (Python):
while 1:
    W,H = map(int,raw_input().split())
    if W == H == 0: break
    wall = [map(int,raw_input().split()) for _ in range(2*H-1)]
    
    dist = [[0]*W for _ in range(H)]
    dist[0][0] = 1
    que = [[0,0]]
    while que:
        x,y = que.pop(0)
        d = dist[y][x]
        for dx,dy in zip([1,0,-1,0],[0,1,0,-1]):
            nx,ny = x+dx, y+dy
            if 0 <= nx < W and 0 <= ny < H:
                if dy == 0:
                    if wall[2*y][min(x,nx)] == 1 or dist[ny][nx] > 0: continue
                if dx == 0:
                    if wall[2*min(y,ny)+1][x] == 1 or dist[ny][nx] > 0: continue
                dist[ny][nx] = d+1
                que.append([nx,ny])
    print dist[-1][-1]

Solution (Python):



while 1:
    ans = 0
    (w, h) = map(int, raw_input().split())
    used = [[False]*w for i in range(h)]
    if h == 0:break
    que = [[0, 0, 1]]
    used[0][0] = True
    vir = []
    hor = []
    for i in range(h):
        vir.append(map(int, raw_input().split()))
        if i == h-1:break
        hor.append(map(int, raw_input().split()))
    while que!=[]:
        y = que[0][0]
        x = que[0][1]
        cost = que[0][2]
        que.pop(0)
        if y==h-1 and x==w-1:
            ans = cost
            break
        if x+1 < w and used[y][x+1] == False and vir[y][x] == 0:
            que.append([y, x+1, cost+1])
            used[y][x+1] = True
        if x-1 >= 0 and used[y][x-1] == False and vir[y][x-1] == 0:
            que.append([y, x-1, cost+1])
            used[y][x-1] = True
        if y+1 < h and used[y+1][x] == False and hor[y][x] == 0:
            que.append([y+1, x, cost+1])
            used[y+1][x] = True
        if y-1 >= 0 and used[y-1][x] == False and hor[y-1][x] == 0:
            que.append([y-1, x, cost+1])
            used[y-1][x] = True
    print ans

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[goal[0]-1][goal[1]-1])

Solution (Python):
import collections
while True:
    W, H = map(int, input().split())
    if (W, H) == (0, 0): break
    cdoor, rdoor = [], []
    cdoor.append(list(map(int, input().split())))
    for _ in range(H-1):
        rdoor.append(list(map(int, input().split())))
        cdoor.append(list(map(int, input().split())))
    
    maze = [[-1 for _ in range(W)] for _ in range(H)]
    maze[0][0] = 1
    que = collections.deque()
    que.append((0, 0))
    drc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    while maze[H-1][W-1] == -1 and len(que) > 0:
        r, c = que.popleft()
        for dr, dc in drc:
            nr, nc = r+dr, c+dc
            if 0 <= nr < H and 0 <= nc < W and ((dc == 0 and rdoor[min(nr, nr-dr)][c] == 0) or (dr == 0 and cdoor[r][min(nc, nc-dc)] == 0)) and maze[nr][nc] == -1:
                maze[nr][nc] = maze[r][c] + 1
                que.append((nr, nc))
    print(maze[H-1][W-1] if maze[H-1][W-1] != -1 else 0)

Solution (Python):
from collections import deque
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
is_wall = [
        (lambda x,y: right[y][x-1]),
        (lambda x,y: bottom[y-1][x]),
        (lambda x,y: right[y][x]),
        (lambda x,y: bottom[y][x]),
        ]
while 1:
    w, h = map(int, raw_input().split())
    if w==h==0: break
    bottom = []
    right = []
    for i in xrange(2*h-1):
        walls = map(int, raw_input().split()) + [1]
        (bottom if i%2 else right).append(walls)
    bottom.append([1] * w)

    dist = [[0]*w for i in xrange(h)]
    deq = deque()
    deq.append((1, 0, 0))
    dist[0][0] = 1
    while deq:
        co, x, y = deq.popleft()
        for k in xrange(4):
            if is_wall[k](x, y): continue
            nx = x + dx[k]; ny = y + dy[k]
            if dist[ny][nx]: continue
            dist[ny][nx] = co+1
            deq.append((co+1, nx, ny))
    print dist[h-1][w-1]

Solution (Python):
from collections import deque


def solve(width, height):
    ver_walls = []
    hor_walls = []

    x_dir = [0, 1, 0, -1]
    y_dir = [-1, 0, 1, 0]

    for i in xrange(2 * height - 1):
        if i % 2 == 0:
            ver_walls.append(map(int, raw_input().split()))
        else:
            hor_walls.append(map(int, raw_input().split()))

    maze = [[True for j in xrange(2 * width + 1)] for i in xrange(2 * height + 1)]

    for i in xrange(len(ver_walls)):
        for j in xrange(len(ver_walls[i])):
            if not ver_walls[i][j]:
                maze[i * 2 + 1][(j  + 1) * 2] = False

    for i in xrange(len(hor_walls)):
        for j in xrange(len(hor_walls[i])):
            if not hor_walls[i][j]:
                maze[(i + 1) * 2][j * 2 + 1] = False

    queue = deque([])

    queue.append((1, 1, 1))

    goal = (2 * width - 1, 2 * height - 1)
    path_goal = 0

    while len(queue) != 0:
        now_x, now_y, path_now = queue.popleft()

        if (now_x, now_y) == goal:
            path_goal = path_now
            break

        for i in xrange(4):
            next_y = now_y + y_dir[i]
            next_x = now_x + x_dir[i]
            if not maze[next_y][next_x]:
                maze[next_y][next_x] = True
                next_y += y_dir[i]
                next_x += x_dir[i]
                maze[next_y][next_x] = True
                queue.append((next_x, next_y, path_now + 1))

    print path_goal


def main():
    while True:
        temp = map(int, raw_input().split())
        width = temp[0]
        height = temp[1]

        if width == 0 and height == 0:
            break

        solve(width, height)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque


def solve(width, height):
    ver_walls = []
    hor_walls = []

    x_dir = [0, 1, 0, -1]
    y_dir = [-1, 0, 1, 0]

    for i in xrange(2 * height - 1):
        if i % 2 == 0:
            ver_walls.append(map(int, raw_input().split()))
        else:
            hor_walls.append(map(int, raw_input().split()))

    maze = [[True for j in xrange(2 * width + 1)] for i in xrange(2 * height + 1)]

    for i in xrange(len(ver_walls)):
        for j in xrange(len(ver_walls[i])):
            if not ver_walls[i][j]:
                maze[i * 2 + 1][(j  + 1) * 2] = False

    for i in xrange(len(hor_walls)):
        for j in xrange(len(hor_walls[i])):
            if not hor_walls[i][j]:
                maze[(i + 1) * 2][j * 2 + 1] = False

    queue = deque([])

    queue.append((1, 1, 1))

    goal = (2 * width - 1, 2 * height - 1)
    path_goal = 0

    while len(queue) != 0:
        now_x, now_y, path_now = queue.popleft()

        if (now_x, now_y) == goal:
            path_goal = path_now
            break

        for i in xrange(4):
            next_y = now_y + y_dir[i]
            next_x = now_x + x_dir[i]
            if not maze[next_y][next_x]:
                maze[next_y][next_x] = True
                next_y += y_dir[i]
                next_x += x_dir[i]
                maze[next_y][next_x] = True
                queue.append((next_x, next_y, path_now + 1))

    print path_goal


def main():
    while True:
        temp = map(int, raw_input().split())
        width = temp[0]
        height = temp[1]

        if width == 0 and height == 0:
            break

        solve(width, height)

if __name__ == '__main__':
    main()

Solution (Python):
def bfs(maze):
    d = [[0] * 70 for i in range(70)]
    d[1][1] = 1
    que = [(1, 1)]
    while 0 < len(que):
        new_que = []
        for x, y in que:
            if x == 2 * w - 1 and y == 2 * h - 1:
                return d[y][x]
            for dx, dy in ((0, 1), (-1, 0), (0, -1), (1, 0)):
                mx, my = x + dx, y + dy
                nx, ny = mx + dx, my + dy
                if nx < 0 and w < nx and ny < 0 and h < ny:
                    continue
                if maze[my][mx] == 0 and d[ny][nx] == 0:
                    new_que.append((nx, ny))
                    d[ny][nx] = d[y][x] + 1
        que = new_que
    return 0

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

    for y in range(1, h * 2):
        a = [int(i) for i in input().split()]
        if y % 2 == 1:
            for x in range(w - 1):
                maze[y][2 * x + 2] = a[x]
        else:
            for x in range(w):
                maze[y][2 * x + 1] = a[x]

    print(bfs(maze))

Solution (Python):
def bfs(maze):
    d = [[0] * (w * 2 + 1) for i in range(h * 2 + 1)]
    d[1][1] = 1
    que = [(1, 1)]
    while que:
        x, y = que.pop(0)
        if x == 2 * w - 1 and y == 2 * h - 1:
            return d[y][x]
        for dx, dy in ((0, 1), (-1, 0), (0, -1), (1, 0)):
            mx, my = x + dx, y + dy
            nx, ny = mx + dx, my + dy
            if nx < 0 and w < nx and ny < 0 and h < ny:
                continue
            if maze[my][mx] == 0 and d[ny][nx] == 0:
                que.append((nx, ny))
                d[ny][nx] = d[y][x] + 1
    return 0

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

    for y in range(1, h * 2):
        a = [int(i) for i in input().split()]
        if y % 2 == 1:
            for x in range(w - 1):
                maze[y][2 * x + 2] = a[x]
        else:
            for x in range(w):
                maze[y][2 * x + 1] = a[x]

    print(bfs(maze))

Solution (Python):
def bfs(maze):
    d = [[0] * 65 for i in range(65)]
    d[1][1] = 1
    que = [(1, 1)]
    while que:
        x, y = que.pop(0)
        if x == 2 * w - 1 and y == 2 * h - 1:
            return d[y][x]
        for dx, dy in ((0, 1), (-1, 0), (0, -1), (1, 0)):
            mx, my = x + dx, y + dy
            nx, ny = mx + dx, my + dy
            if nx < 0 and w < nx and ny < 0 and h < ny:
                continue
            if maze[my][mx] == 0 and d[ny][nx] == 0:
                que.append((nx, ny))
                d[ny][nx] = d[y][x] + 1
    return 0

while True:
    w, h = map(int, input().split())
    maze = [[0] * 65 for i in range(65)]
    if w == h == 0:
        break
    for x in range(w * 2 + 1):
        maze[0][x] = maze[h * 2][x] = 1
    for y in range(h * 2 + 1):
        maze[y][0] = maze[y][w * 2] = 1

    for y in range(1, h * 2):
        a = [int(i) for i in input().split()]
        if y % 2 == 1:
            for x in range(w - 1):
                maze[y][2 * x + 2] = a[x]
        else:
            for x in range(w):
                maze[y][2 * x + 1] = a[x]

    print(bfs(maze))

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[goal[0]-1][goal[1]-1])