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 collections import deque
while True:
    ans = 0
    vertical = []
    horizantal = []
    w,h =map(int,input().split())
    G = [[10**6 for i in range(w)] for j in range(h)]
    if (w,h) == (0,0):
        break 
    for i in range(2*h-1):
        if i%2==0:
            vertical.append(list(map(int,input().split())))
        else:
            horizantal.append(list(map(int,input().split())))
    queue = deque([(0,0)])
    G[0][0] = 0
    while len(queue) != 0:
        now = queue.popleft()
        dw = [(0,-1),(0,1)]
        dh = [(1,0),(-1,0)]
        for move in dw:
            nexte = (now[0], now[1]+move[1])
            if nexte[1] < 0 or nexte[1] >= w:
                continue
            else:
                if move[1] == 1:
                    if vertical[now[0]][now[1]] == 0:
                        if G[nexte[0]][nexte[1]] > G[now[0]][now[1]] +1:
                            G[nexte[0]][nexte[1]] = G[now[0]][now[1]] + 1
                            queue.append((nexte[0],nexte[1]))
                elif move[1] == -1:
                    if vertical[nexte[0]][nexte[1]] == 0:
                        if G[nexte[0]][nexte[1]] > G[now[0]][now[1]] +1:
                            G[nexte[0]][nexte[1]] = G[now[0]][now[1]] + 1
                            queue.append((nexte[0],nexte[1]))          
        for move in dh:
            nexte = (now[0] + move[0], now[1])
            if nexte[0]<0 or nexte[0] >= h:
                continue
            else:
                if move[0] == 1:
                    if horizantal[now[0]][now[1]] == 0:
                    
                        if G[nexte[0]][nexte[1]] > G[now[0]][now[1]] +1:
                            G[nexte[0]][nexte[1]] = G[now[0]][now[1]] + 1
                            queue.append((nexte[0],nexte[1]))
                elif move[0] == -1:
                    if horizantal[nexte[0]][nexte[1]] == 0:
                        if G[nexte[0]][nexte[1]] > G[now[0]][now[1]] +1:
                            G[nexte[0]][nexte[1]] = G[now[0]][now[1]] + 1
                            queue.append((nexte[0],nexte[1]))
    if G[h-1][w-1] == 10**6:
        print(0)
    else:
        print(G[h-1][w-1]+1)

Solution (Python):
from collections import deque


def bfs(start):
    Q = deque()
    Q.append(start)
    child = deque()
    dist[start[1]][start[0]] = 0

    while Q:
        x, y = Q.popleft()

        for i in range(4):
            child.clear()
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= W or ny < 0 or ny >= H:
                continue
            if G[y][x][i] == 1:
                continue
            if dist[ny][nx] != -1:
                continue

            child.append((nx, ny))

            if len(child) > 0:
                for c in child:
                    dist[c[1]][c[0]] = dist[y][x] + 1
                    Q.append(c)


W, H = map(int, input().split())
while not (W == 0 and H == 0):
    G = [[[0 for _ in range(4)] for _ in range(W)] for _ in range(H)]

    w = []
    h = []
    for i in range(H - 1):
        w.append(list(map(int, input().split())))
        h.append(list(map(int, input().split())))
    w.append(list(map(int, input().split())))

    for i in range(H):
        for j in range(W):
            if j < W - 1:
                
                G[i][j][0] = w[i][j]
            else:
                G[i][j][0] = 1
            if i < H - 1:
                
                G[i][j][1] = h[i][j]
            else:
                G[i][j][1] = 1
            if j - 1 >= 0:
                
                G[i][j][2] = w[i][j - 1]
            else:
                G[i][j][2] = 1
            if i - 1 >= 0:
                
                G[i][j][3] = h[i - 1][j]
            else:
                G[i][j][3] = 1

    dist = [[-1 for _ in range(W)] for _ in range(H)]

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

    bfs((0, 0))

    print(dist[H - 1][W - 1] + 1)

    W, H = map(int, input().split())

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


def BFS():
    color=[["white" for _ in range(w*2-1)] for _ in range(h*2-1)]
    D=[[inf for _ in range(w*2-1)] for _ in range(h*2-1)]

    color[0][0]="gray"
    D[0][0]=1

    queue=deque([[0,0]])
    while len(queue)>0:
        a,b=queue.popleft()
        for c,d in [[-1,0],[1,0],[0,-1],[0,1]]:
            X,Y=a+c*2,b+d*2
            if 0<=X<h*2-1 and 0<=Y<w*2-1:
                if C[X-c][Y-d]=="|" or C[X-c][Y-d]=="_" or color[X][Y]!="white":continue
                else:
                    color[X][Y]="gray"
                    D[X][Y]=min(D[a][b]+1,D[X][Y])
                    queue.append([X,Y])
        color[a][b]="black"

    return D[-1][-1]


while 1:
    w,h=map(int,input().split())
    if w==0 and h==0:break
    C=[["." for _ in range(w*2-1)] for _ in range(h*2-1)]
    for i in range(h*2-1):
        for j,k in enumerate(list(map(int,input().split()))):
            if i%2==0:C[i][1+j*2]="|" if k==1 else "."
            else:C[i][j*2]="_" if k==1 else "."
    D=BFS()
    print(D if D!=inf else 0)

Solution (Python):
from collections import deque

while True:
  w,h = map(int,input().split())
  ww = w*2-1
  hh = h*2-1
  if w == 0:
    break
  field = [input() for _ in range(hh)]
  d = [[0]*(ww) for _ in range(hh)]
  q = deque()
  q.append([0,0])
  dmov = [(-1,0),(1,0),(0,-1),(0,1)]
  d[0][0] = 1
  
  while len(q) > 0:
    node = q.popleft()
    x = node[0]
    y = node[1]
    c = d[y][x]
    for i,j in dmov:
      xx = x+i
      yy = y+j
      xxx = xx+i
      yyy = yy+j
      if 0<=xx<ww and 0<=yy<hh:
        if d[yyy][xxx] == 0 and field[yy][xx] == "0":
          d[yyy][xxx] = c+1
          q.append([xxx,yyy])
  print(d[hh-1][ww-1])

Solution (Python):


from pprint import pprint
from collections import deque
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline


def adj(i, j):
    up, down = [i - 1, j], [i + 1, j]
    left, right = [i, j - 1], [i, j + 1]
    res = []
    for i_next, j_next in up, down, left, right:
        if 0 <= i_next < height and 0 <= j_next < width:
            if [i_next, j_next] == left:
                if walls[i * 2][j - 1] == 0:
                    res.append([i_next, j_next])
            elif [i_next, j_next] == right:
                if walls[i * 2][j] == 0:
                    res.append([i_next, j_next])
            elif [i_next, j_next] == up:
                if walls[2 * i - 1][j] == 0:
                    res.append([i_next, j_next])
            else:
                if walls[2 * i + 1][j] == 0:
                    res.append([i_next, j_next])
    return res


def bfs(que, dist):
    while len(que) > 0:
        i, j = que.popleft()
        for i_next, j_next in adj(i, j):
            if dist[i_next][j_next] == -1:
                dist[i_next][j_next] = dist[i][j] + 1
                que.append([i_next, j_next])
    return dist


while True:
    width, height = map(int, input().split())
    if width == 0 and height == 0:
        break
    walls = []
    for _ in range(2 * height - 1):
        line = list(map(int, input().split()))
        walls.append(line)
    

    maze = [[-1 for j in range(width)] for i in range(height)]
    que = deque()
    dist = [[-1 for j in range(width)] for i in range(height)]

    start = [0, 0]
    que.append(start)
    dist[0][0] = 0

    dist = bfs(que, dist)
    print(dist[height - 1][width - 1] + 1)

Solution (Python):
from collections import deque

def cat_go(x,y,nx,ny):
    if x == nx:
        return 1-wall[2*x][min(ny,y)]
    else:
        return 1-wall[2*min(x,nx)+1][y]

def bfs():
    global mapp
    mapp[0][0] = 1
    que = deque()
    que.append([0,0])
    while que:
        place = que.popleft()
        x = place[0];y = place[1]
        
        if x == h-1 and y == w-1:
            return mapp[x][y]
        for d in [[1,0],[0,1],[-1,0],[0,-1]]:
            nx = x + d[0];ny = y + d[1]
            
            if not (0<=nx and nx<h and 0<=ny and ny<w):continue
            if not cat_go(x,y,nx,ny):continue
            
            if mapp[nx][ny] != 0:continue
            
            mapp[nx][ny] = mapp[x][y]+1
            que.append([nx,ny])
    return 0

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

Solution (Python):
from collections import Counter, deque, defaultdict
import sys
input = sys.stdin.readline
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def main():
    while True:
        w, h = map(int, input().split())
        if w == 0:
            exit()
        wall = [list(map(int, input().split())) for _ in range(2 * h - 1)]
        check = [[0] * w for _ in range(h)]
        check[0][0] = 1
        q = deque([])
        q.append((0, 0))
        while q:
            y, x = q.popleft()
            for i in range(4):
                ny = y + dy[i]
                nx = x + dx[i]
                if nx < 0 or w-1 < nx or ny < 0 or h-1 < ny:
                    continue
                if check[ny][nx] > 0:
                    continue
                if wall[y + ny][(x + nx) // 2] == 1:
                    continue
                check[ny][nx] = check[y][x] + 1
                q.append((ny,nx))
        print(check[h-1][w-1])


if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: print('Yes' if b else 'No')
YESNO=lambda b: print('YES' if b else 'NO')

def main():
    while True:
        W,H=map(int,input().split())
        if W==H==0:
            break
        edge=[[[] for _ in range(W)] for _ in range(H)]
        for i in range(2*H-1):
            l=list(map(int,input().split()))
            for j,x in enumerate(l):
                if x==0:
                    if i%2==0:
                        edge[i//2][j].append((i//2,j+1))
                        edge[i//2][j+1].append((i//2,j))
                    else:
                        edge[i//2][j].append((i//2+1,j))
                        edge[i//2+1][j].append((i//2,j))
        d=[[INF]*W for _ in range(H)]
        d[0][0]=1
        que=deque()
        que.append((0,0))
        ans=INF
        while que:
            y,x=que.popleft()
            for ny,nx in edge[y][x]:
                if d[ny][nx]>d[y][x]+1:
                    d[ny][nx]=d[y][x]+1
                    que.append((ny,nx))
                    if ny==H-1 and nx==W-1:
                        ans=min(ans,d[ny][nx])
        print(ans if ans!=INF else 0)
                        
        
        

if __name__ == '__main__':
    main()

Solution (Python):
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
import time
from bisect import bisect_left, insort_left, bisect_right
import sys
import random
import itertools

input = sys.stdin.readline
_NUMINT_ALL = list(range(10))
_START_TIME = time.time()
INDEX_KETA = 10**12

def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is None:
        return

    if isinstance(ans, tuple):
        split_print_space(ans)
    else:
        print(ans)


def solve():

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

        edge = {}
        for x in range(w):
            for y in range(h):
                edge[x, y] = []

        for i in range(h*2-1):
            if i%2 == 0: 
                data = iip(True)
                y = i // 2
                for j in range(w-1):
                    x1 = j
                    x2 = j + 1
                    if data[j] == 0:
                        edge[x1, y].append((x2, y))
                        edge[x2, y].append((x1, y))

            else: 
                data = iip()
                y1 = i // 2
                y2 = y1 + 1
                for j in range(w):
                    x = j
                    if data[j] == 0:
                        edge[x, y1].append((x, y2))
                        edge[x, y2].append((x, y1))

            

        old_route = {(0, 0):True}
        que = deque()
        que.append((0, 0, 1))

        fin = False
        while True:
            if not que:
                print(0)
                break

            x, y, depth = que.popleft()
            

            for x_target, y_target in edge[x, y]:
                if (x_target, y_target) == (w-1, h-1):
                    print(depth+1)
                    fin = True
                    break

                if (x_target, y_target) in old_route:
                    continue
                old_route[x_target, y_target] = True
                que.append((x_target, y_target, depth+1))

            if fin:
                break


















def kiriage_warizan(a, b):
    return -(-a//b)


def iip(listed=False):  
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1 and listed is False:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=True, num_only=True):  
    if isinstance(l, list):
        l = l[0] 
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def index_sorted(sorted_list, target):
    idx = bisect_left(sorted_list, target)
    if idx != len(sorted_list) and sorted_list[idx] == target:
        return idx
    else:
        return False


def time_debug_10percent():
    a = random.randint(0, 9)
    if a == 9:
        sys.exit()

def time_debug(t):
    time.sleep(_START_TIME + t - time.time())
    sys.exit()


def make_graph_edge_flat(N):  
    ret = []
    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  
    if index >= len(l):                      
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  
    return "".join(sorted(s))


def iip_ord(startcode="a"):  
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  
    for i in s:
        print(i)


def bitall(N):  
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        
        pass
    return ret


def inv(n, mod):  
    return power(n, mod - 2)


def power(n, p, mod_=mod):  
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left", seido = 1): 
    l = left
    r = right
    if seido == 1:
        x = (l + r) // 2
    else:
        x = (l + r) / 2
    while r-l > seido:
        
        if seido == 1:
            x = (l + r) // 2
        else:
            x = (l + r) / 2
        if func(x) == target:
            if side == "left":
                r=x
            else:
                l=x


        elif func(x) > target:
            r = x
        else:
            
            l = x

    
    if side == "left" and func(r) == target:
        return r
    elif side != "left" and func(l) == target:
        return l
    elif side == "left":
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r


class UfTree():
    def __init__(self, maxnum):
        self.parent = list(range(maxnum))
        self._size = [1] * maxnum
        self.rank = [0] * maxnum

    def size(self, a):
        return self._size[self.root(a)]

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                
                
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return self

        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        return self

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

while True:
  W, H = map(int, input().split())
  if (W,H) == (0,0):
    exit()
  
  
  adj = [[] for _ in range(W*H)]
  colWall = [None] * H
  rowWall = [None] * (H-1)
  
  for i in range(H):
    colWall[i] = list(map(int, input().split()))
    if i < H-1:
      rowWall[i] = list(map(int, input().split()))
    
  dx = [-1,1,0,0]
  dy = [0,0,-1,1]
  
  for i in range(H):
    for j in range(W):
      for k in range(4):
        y = i + dy[k]
        x = j + dx[k]
        if 0<=x<W and 0<=y<H:
          if k == 0:
            if colWall[i][j-1] == 0:
              adj[W*i+j].append(W*y+x)
          elif k == 1:
            if colWall[i][j] == 0:
              
              adj[W*i+j].append(W*y+x)
          elif k == 2:
            if rowWall[i-1][j] == 0:
              adj[W*i+j].append(W*y+x)
          else:
            if rowWall[i][j] == 0:
              
              adj[W*i+j].append(W*y+x)
  
  
  queue = deque([0])
  visit = [0] * (W*H)
  visit[0] = 1
  
  while queue:
    now = queue.popleft()
    for u in adj[now]:
      if visit[u] < 1:
        queue.append(u)
        visit[u] = visit[now] + 1
  print(visit[W*H-1])

Solution (Python):
from collections import deque
while True:
    W, H = map(int, input().split())
    if W==0 and H==0:
        break
    
    grid = [ [ [0]*4 for _ in range(W)] for _ in range(H)] 
    
    
    for i in range(H):
        grid[i][0][0] = 1
        grid[i][-1][1] = 1
    
    for i in range(W):
        grid[0][i][2] = 1
        grid[-1][i][3] = 1
    
    
    
    

    
    for i in range(2*H-1):
        a = list(map(int, input().split()))
        
        if i%2==0:
            for j in range(W-1):
                if a[j] == 1:
                    grid[i//2][j][1] = 1
                    grid[i//2][j+1][0] = 1
        
        else:
            for j in range(W):
                if a[j] == 1:
                    grid[i//2][j][3] = 1
                    grid[i//2+1][j][2] = 1
        
    

    dist = [[-1]*W for _ in range(H)]
    dist[0][0] = 0
    

    que = deque()
    que.append([0,0])

    
    d = [[0,-1],[0,1],[-1,0],[1,0]]

    while que:
        
        y,x = que.popleft()
        for i in range(4):
            if grid[y][x][i] == 0:
                dy = y + d[i][0]
                dx = x + d[i][1]
                if dist[dy][dx] == -1:
                    que.append([dy,dx])
                    dist[dy][dx] = dist[y][x]+1
    
    if dist[-1][-1] == -1:
        print(0)
    else:
        print(dist[-1][-1]+1)

Solution (Python):


from collections import deque


class Point:
    def __init__(self):
        super().__init__()
        self.up = 1
        self.down = 1
        self.left = 1
        self.right = 1


def solve(W, H):
    Points = {}
    for i in range(H):
        for j in range(W):
            point = Point()
            Points[(i, j)] = point

    for i in range(H * 2 - 1):
        if i % 2 == 0:
            
            walls = list(map(int, input().split()))
            for j, wall in enumerate(walls):
                Points[(i//2, j)].right = wall
                Points[(i//2, j + 1)].left = wall
        else:
            
            walls = list(map(int, input().split()))
            for j, wall in enumerate(walls):
                Points[(i//2, j)].down = wall
                Points[(i//2 + 1, j)].up = wall

    queue = deque()
    queue.appendleft((0, 0, 1))
    checked = set()
    goal = (H-1, W-1)

    result = 0
    while queue:
        
        i, j, d = queue.pop()
        if (i, j) in checked:
            continue
        checked.add((i, j))

        if (i, j) == goal:
            result = d
            break

        point = Points[(i, j)]
        tmp_d = d+1
        if point.up == 0:
            queue.appendleft((i-1, j, tmp_d))
        if point.down == 0:
            queue.appendleft((i+1, j, tmp_d))
        if point.left == 0:
            queue.appendleft((i, j-1, tmp_d))
        if point.right == 0:
            queue.appendleft((i, j+1, tmp_d))

    print(result)


if __name__ == "__main__":
    while True:
        W, H = map(int, input().split())
        if W == 0 and H == 0:
            break

        solve(W, H)

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

from collections import deque
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

while True:
    w, h = na()
    if w == 0 and h == 0:
        break
    maze = [
        [0] * (w - 1) + [1], 
        *[na() if x % 2 != 0 else [1] + na() + [1] for x in range(2 * h - 1)],
        [1] + [0] * (w - 1)
    ]
    d = [[0] * w for _ in range(h)]
    que = deque()
    d[0][0] = 1
    que.append((0, 0))
    while que:
        y, x = que.popleft()
        t = y * 2 + 1
        t1 = t - 1
        t2 = t
        t3 = t + 1
        if maze[t1][x] == 0 and y-1 >= 0 and d[y-1][x] == 0:
            que.append((y-1, x))
            d[y-1][x] = d[y][x] + 1
        if maze[t2][x] == 0 and x-1 >= 0 and d[y][x-1] == 0:
            que.append((y, x-1))
            d[y][x-1] = d[y][x] + 1
        if maze[t2][x+1] == 0 and x+1 < w and d[y][x+1] == 0:
            que.append((y, x+1))
            d[y][x+1] = d[y][x] + 1
        if maze[t3][x] == 0 and y+1 < h and d[y+1][x] == 0:
            que.append((y+1, x))
            d[y+1][x] = d[y][x] + 1
    print(d[h-1][w-1])

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


dhl = [-1, 1]
dw = [(0, 1), (0, -1)]


def getNeighbor(h, w):
    
    if h < H - 1 and vertical[h][w] == 0:
        yield (h + 1, w)
    if h > 0 and vertical[h - 1][w] == 0:
        yield (h - 1, w)
    if w > 0 and horizon[h][w - 1] == 0:
        yield (h, w - 1)
    if w < W - 1 and horizon[h][w] == 0:
        yield (h, w + 1)


def solve():
    mp = [[0] * W for _ in range(H)]
    Q = deque()
    Q.append((0, 0))
    while Q:
        
        nh, nw = Q.popleft()
        for h, w in getNeighbor(nh, nw):
            if mp[h][w] == 0:
                mp[h][w] = mp[nh][nw] + 1
                Q.append((h, w))

    return 0 if mp[H - 1][W - 1] == 0 else mp[H - 1][W - 1] + 1


ans = []
while True:
    W, H = inpl()
    if W == H == 0:
        break
    horizon = []
    vertical = []
    for _ in range(H - 1):
        horizon.append(inpl())
        vertical.append(inpl())
    horizon.append(inpl())
    ans.append(solve())

for a in ans:
    print(a)

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
from collections import deque
y_drct = [-1,0,1,0]
x_drct = [0,1,0,-1]
def wall(y,x,i):
    if i==0:
        if yw[y-1][x] == 0:return 1
        else: return 0
    if i==2:
        if yw[y][x] == 0:return 1
        else: return 0
    if i==1:
        if tw[y][x] == 0:return 1
        else: return 0
    if i==3:
        if tw[y][x-1] == 0:return 1
        else: return 0
while 1:
    w,h = mi()
    if w == 0 and h == 0:
        break
    tw = []
    yw = []
    for i in range(h-1):
        tw.append(li())
        yw.append(li())
    tw.append(li())
    b = [[-1]*w for i in range(h)]
    l = deque()
    l.append((0,0))
    b[0][0] = 1
    while len(l) > 0:
        cy,cx = l.popleft()
        if cy == h-1 and cx == w-1:
            break
        for i in range(4):
            ny,nx = cy+y_drct[i],cx+x_drct[i]
            if 0 <= ny < h and 0 <= nx < w:
                if b[ny][nx] == -1:
                    if wall(cy,cx,i):
                        l.append((ny,nx))
                        b[ny][nx] = b[cy][cx]+1
    if b[h-1][w-1]==-1:
        print(0)
    else:
        print(b[h-1][w-1])