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
import math
from collections import defaultdict, deque
from copy import deepcopy
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    move = [[1,0],[0,1],[-1,0],[0,-1]]
    while True:
        W, H = MI()
        result = 0
        if W == 0 and H == 0:
            sys.exit()
        maze = [LI() for i in range(2*H-1)]
        goal = [H-1,W-1]
        d = Init(H,W,-1)
        dq = deque()
        dq.append([0,0])
        d[0][0] = 0
        while dq:
            ht, wt = dq.popleft()
            for h, w in move:
                h += ht
                w += wt
                if h >= 0 and w >= 0 and h < H and w < W and d[h][w] == -1:
                    if ht != h:
                        if maze[2*min(ht, h)+1][w] == 0:
                            dq.append([h,w])
                            d[h][w] = d[ht][wt]+1
                            if h == goal[0] and w == goal[1]:
                                result = d[h][w]+1
                                break
                    elif wt != w:
                        
                        if maze[2*h][min(w, wt)] == 0:
                            dq.append([h,w])
                            d[h][w] = d[ht][wt]+1
                            if h == goal[0] and w == goal[1]:
                                result = d[h][w]+1
                                break
            else:
                continue
            break
        print(result)

    
if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque

input = sys.stdin.readline
digtmp = [(0,1), (1,0), (0,-1), (-1,0)]

def solve():
    W, H = map(int, input().split())
    if W == 0 and H == 0:
        return -1
    h_cnt = 0
    wallset = set()
    for i in range(2*H-1):
        wallflag = list(map(int, input().split()))
        if i%2 == 0:
            for j, wf in enumerate(wallflag):
                if wf == 1:
                    wallset.add( frozenset( ((h_cnt, j), (h_cnt, j+1)) ) )
        else:
            for j, wf in enumerate(wallflag):
                if wf == 1:
                    wallset.add( frozenset( ((h_cnt, j), (h_cnt+1, j)) ) )
            h_cnt += 1

    
    field = [[0]*W for i in range(H)]
    field[0][0] = 1
    que = deque([(0,0)])
    while True:
        fr_x, fr_y = que.popleft()
        cnt = field[fr_x][fr_y]
        for d_x, d_y in digtmp:
            to_x = fr_x + d_x
            to_y = fr_y + d_y
            if 0 <= to_x < H and 0 <= to_y < W:
                wallcheck = set(((fr_x, fr_y), (to_x, to_y)))
                if wallcheck in wallset:
                    continue
                if field[to_x][to_y] == 0:
                    field[to_x][to_y] = cnt + 1
                    que.append((to_x, to_y))
        if len(que) == 0:
            break
    
    
    ans = field[H-1][W-1]
    print(ans)
    return 0

def main():
    status = 0
    while status == 0:
        status = solve()
            
if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

while True:
  W, H = map(int, input().split())
  if W == 0 and H == 0:
    break
  
  wall_v = []
  wall_h = []

  wall_h.append([1] * W)
  for _ in range(H-1):
    vertical = list(map(int, input().split()))
    vertical.insert(0, 1)
    vertical.append(1)
    wall_v.append(vertical)
    wall_h.append(list(map(int, input().split())))
  vertical = list(map(int, input().split()))
  vertical.insert(0, 1)
  vertical.append(1)
  wall_v.append(vertical)
  wall_h.append([1] * W)

  q = deque()
  dist = [[0] * W for _ in range(H)]

  dist[0][0] = 1
  q.append([0, 0])

  while len(q) != 0:
    v = q.popleft()
    udlr = ([-1, 0], [1, 0], [0, -1], [0, 1])

    for move in udlr:
      if move == [-1, 0]:
        if wall_h[v[0]][v[1]] == 1:
          continue
      if move == [1, 0]:
        if wall_h[v[0]+1][v[1]] == 1:
          continue
      if move == [0, -1]:
        if wall_v[v[0]][v[1]] == 1:
          continue
      if move == [0, 1]:
        if wall_v[v[0]][v[1]+1] == 1:
          continue
      nv = [0, 0]
      nv[0], nv[1] = v[0] + move[0], v[1] + move[1]
      if dist[nv[0]][nv[1]] != 0:
        continue
      dist[nv[0]][nv[1]] = dist[v[0]][v[1]] + 1
      q.append(nv)

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

Solution (Python):
from collections import deque

while True:
    w, h = map(int, input().split())
    if w == h == 0:
        break
    li = [list(map(int, input().split())) for _ in range(2*h-1)]
    
    Map = [['x'] * (w*2+1)]
    Map += [['x'] + ['.'] * (w*2-1) + ['x'] for _ in range(2*h-1)]
    Map += [['x'] * (w*2+1)]
    
    for i in range(2*h+1):
        for j in range(2*w+1):
            if i%2 == 0 and j%2 == 0:
                Map[i][j] = 'x'
    
    for k in range(2*h-1):
        if k%2 == 0:
            for i in range(len(li[k])):
                if li[k][i] == 1:
                    Map[k+1][i*2+2] = 'x'
        else:
            for i in range(len(li[k])):
                if li[k][i] == 1:
                    Map[k+1][i*2+1] = 'x'
    
    moved = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    stack = deque([(1,1)])
    Map[1][1] = 1
    while stack:
        x, y = stack.popleft()
        for s, t in moved:
            if Map[x+s][y+t] == '.':
                stack.append((x+s, y+t))
                if (x+s) % 2 == 0 or (y+t) % 2 == 0:
                    Map[x+s][y+t] = Map[x][y]
                else:
                    Map[x+s][y+t] = Map[x][y] + 1
    
    ans = Map[2*h-1][-2]
    if ans == '.':
        print(0)
    else:
        print(ans)

Solution (Python):
from collections import deque

U = 0
R = 1
D = 2
L = 3
CNT = 4

directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]

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

    maze = [[[1, 1, 1, 1, float('inf')] for _ in range(W)] for _ in range(H)]
    maze[0][0][U] = 0
    maze[0][0][CNT] = 0
    maze[H-1][W-1][D] = 0
    for h in range(H*2-1):
        A = list(map(int, input().split()))
        
        if h % 2 == 0:
            for w, a in enumerate(A):
                if a == 0:
                    maze[h//2][w][R] = 0
                    maze[h//2][w+1][L] = 0
        
        else:
            for w, a in enumerate(A):
                if a == 0:
                    maze[h//2][w][D] = 0
                    maze[h//2+1][w][U] = 0

    q = deque([[0, 0]])
    while q:
        y, x = q.popleft()
        for dy, dx in directions:
            if 0 <= y+dy < H and 0 <= x+dx < W:
                if (dy == 1 and maze[y][x][D] == 0) or \
                    (dy == -1 and maze[y][x][U] == 0) or \
                    (dx == 1 and maze[y][x][R] == 0) or \
                    (dx == -1 and maze[y][x][L] == 0):
                    if maze[y+dy][x+dx][CNT] > maze[y][x][CNT] + 1:
                        maze[y+dy][x+dx][CNT] = maze[y][x][CNT] + 1
                        q.append([y+dy, x+dx])

    if maze[H-1][W-1][CNT] == float('inf'):
        print(0)
    else:
        print(maze[H-1][W-1][CNT]+1)

Solution (Python):
from collections import deque
ans = []
while True:
    W, H = map(int, input().split())
    if (W, H) == (0, 0): break
    tate = []
    yoko = []
    for i in range(2*H-1):
        if i%2 == 0:
            tate.append(list(map(int, input().split())))
        else:
            yoko.append(list(map(int, input().split())))
    q = deque()
    q.append((0, 0))
    dis = [[-1]*W for _ in range(H)]
    dis[0][0] = 1
    while q:
        h, w = q.popleft()
        for dw, dh in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            nw, nh = w+dw, h+dh
            if not (0 <= nw < W and 0 <= nh < H and dis[nh][nw] == -1): continue
            if dw != 0 and tate[h][(w+nw)//2] == 1: continue
            if dh != 0 and yoko[(h+nh)//2][w] == 1: continue
            dis[nh][nw] = dis[h][w]+1
            q.append((nh, nw))
    if dis[H-1][W-1] != -1:
        ans.append(dis[H-1][W-1])
    else:
        ans.append(0)
print(*ans, sep="\n")

Solution (Python):
from collections import deque

def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    dist = [[0 for _ in range(w)] for _ in range(h)]
    dist[0][0] = 1

    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return visited[y][x]
        if x == w-1 and y == h-1:
            break
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            block = 0
            if new_x < 0 or new_y < 0 or w <= new_x or h <= new_y:
                continue  

            if j == 1: block = horizontal[y][x]
            if j == -1: block = horizontal[y-1][x]
            if k == 1: block = vertical[y][x]
            if k == -1: block = vertical[y][x-1]

            if block == 0 and \
                visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
                dist[new_y][new_x] = dist[y][x]+1
    return dist[h-1][w-1]

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

Solution (Python):
import sys
from collections import deque


while True:
    w,h=map(int,input().split())
    if w==h==0:
        sys.exit()
    
    
    
    Vert=[]
    Hori=[]
    for i in range(2*h-1):
        
        if i%2==0:
            Vert.append(list(map(int,input().split())))
        
        else:
            Hori.append(list(map(int,input().split())))
    
    
    def sur(v): 
        vx=v[0]
        vy=v[1]
        preE=[(vx-1,vy),(vx+1,vy),(vx,vy-1),(vx,vy+1)]
        E=[]
        if 0<vx:
            if Hori[vx-1][vy]==0:
                E.append((vx-1,vy))
        if vx<h-1:
            if Hori[vx][vy]==0:
                E.append((vx+1,vy))
        if 0<vy:
            if Vert[vx][vy-1]==0:
                E.append((vx,vy-1))
        if vy<w-1:
            if Vert[vx][vy]==0:
                E.append((vx,vy+1))
        return E

    
    dist=[[0]*w for i in range(h)]
    q=deque()

    dist[0][0]=1
    q.append((0,0))
    while q:
        now=q.popleft()
        for next in sur(now):
            if dist[next[0]][next[1]]>0:
                continue
            q.append(next)
            dist[next[0]][next[1]]=dist[now[0]][now[1]]+1

            if next==(h-1,w-1):
                print(dist[h-1][w-1])
                break
        else:
            continue
        break
    else:
        print(0)

Solution (Python):
def main():
    w,h=map(int,input().split())
    if w==0 and h==0 : exit()
    
    con=[[[] for j in range(w)] for _ in range(h)]

    token=0 
    for i in range(2*h-1):
        lst=input().split()
        if token==0 :
            for j,x in enumerate(lst):
                if x=="0":
                    con[i//2][j].append((i//2,j+1))
                    con[i//2][j+1].append((i//2,j))
            token=1
        else :
            for j,x in enumerate(lst):
                if x=="0" :
                    con[(i+1)//2][j].append(((i-1)//2,j))
                    con[(i-1)//2][j].append(((i+1)//2,j))
            token=0
        
    
    seen=[[-1]*w for _ in range(h)]
    seen[0][0]=1
    bfs_new=[(0,0)]
    token=1
    
    while bfs_new:
        bfs_old=bfs_new[:]
        bfs_new=[]
        token+=1
        for ax,ay in bfs_old:
            for bx,by in con[ax][ay]:
                if seen[bx][by]>=0 : continue
                seen[bx][by]=token
                bfs_new.append((bx,by))
    
    if seen[h-1][w-1]==-1 : print(0)
    else : print(seen[h-1][w-1])

while 1:
    main()

Solution (Python):
def solve(w,h,row,col):
    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:
            return 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:
        return 0

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())
    print(solve(w,h,row,col))

Solution (Python):
from collections import deque

def get_adj(pos):
    return [(pos[0]-1, pos[1]),
            (pos[0]+1, pos[1]),
            (pos[0], pos[1]-1),
            (pos[0], pos[1]+1),
            ]

def can_go(pos, adj, walls):
    if (pos, adj) not in walls:
        return False
    if walls[(pos, adj)] == 0:
        return True
    return False

def solve(W, H):
    walls = {}
    for r in range(2*H - 1):
        l = list(map(int, input().split()))
        if r % 2 == 0:
            for c in range(len(l)):
                left = (r//2, c)
                right = (r//2, c+1)
                walls[(left, right)] = l[c]
                walls[(right, left)] = l[c]
        else:
            for c in range(len(l)):
                up = (r//2, c)
                down = (r//2 + 1, c)
                walls[(up, down)] = l[c]
                walls[(down, up)] = l[c]
    start = (0, 0)
    goal = (H-1, W-1)
    q = deque()
    q.append((start, 0))
    visited = set()
    while q:
        pos, dist = q.popleft()
        if pos in visited:
            continue
        if pos == goal:
            print(dist + 1)
            return
        visited.add(pos)
        for adj in get_adj(pos):
            if can_go(pos, adj, walls):
                q.append((adj, dist+1))

    print(0)
    return

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

Solution (Python):
import sys
from collections import deque

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

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

    wall_tate = []
    wall_yoko = []

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

    moves = [1, -1]

    q = deque([[0, 0]])

    while q:
        curr = q.popleft()

        
        for m in moves:
            nx, ny = curr[0] + m, curr[1]
            if 0 <= nx < h and 0 <= ny < w and grid[nx][ny] == 0:
                if wall_tate[min(curr[0], nx)][ny] == 0:
                    grid[nx][ny] = grid[curr[0]][curr[1]] + 1
                    q.append([nx, ny])

        
        for m in moves:
            nx, ny = curr[0], curr[1] + m
            if 0 <= nx < h and 0 <= ny < w and grid[nx][ny] == 0:
                if wall_yoko[nx][min(curr[1], ny)] == 0:
                    grid[nx][ny] = grid[curr[0]][curr[1]] + 1
                    q.append([nx, ny])

    print(grid[-1][-1])

Solution (Python):
from collections import deque

ans = []
while True:
  w,h = map(int,input().split())
  if w==h==0: 
    
    
    exit()

  maze = []
  for k in range(h):
    
    row = [ [0,0] for _ in range(w) ]
    
    for i in range(2):
      if i==0:
        
        v = list(map(int,input().split()))
        for j in range(w-1):
          if v[j] == 1:
            row[j][1] = 1
      else:
        
        if k == h-1: continue
        v = list(map(int,input().split()))
        for j in range(w):
          if v[j] == 1:
            row[j][0] = 1

    maze.append(row)

  dist = [ [-1]*w for _ in range(h) ]
  dist[0][0] = 1
  q = deque([(0,0)])

  while q:
    r,c = q.popleft()

    directions = []

    
    if maze[r][c][0] == 0:
      directions.append((1,0))

    
    if maze[r][c][1] == 0:
      directions.append((0,1))

    
    if r-1>=0 and maze[r-1][c][0] == 0:
      directions.append((-1,0))

    
    if c-1>=0 and maze[r][c-1][1] == 0:
      directions.append((0,-1))


    for x,y in directions:
      nr,nc = r+x,c+y
      
      if 0 <= nr < h and 0 <= nc < w:
        if dist[nr][nc] != -1: continue
        if (nr,nc) in q: continue
        dist[nr][nc] = dist[r][c] + 1
        if nr == h-1 and nc == w-1:
          break
        else:
          q.append((nr,nc))

  if dist[h-1][w-1] == -1:
    ans.append(0)
    print(0)
  else:
    ans.append(dist[h-1][w-1])
    print(dist[h-1][w-1])


for a in ans:
  print(a)

Solution (Python):
from collections import deque
ans=[]
while True:
    w,h=map(int,input().split())
    if w==0 and h==0:
        break
    lr=[]
    ud=[]
    dist=[[-1]*(w+2) for _ in range(h+2)]
    dist[1][1]=1
    lr.append([1 for _ in range(w+1)])
    ud.append([1 for _ in range(w+2)])
    lr.append([1]+list(map(int,input().split()))+[1])
    for i in range(h-1):
        ud.append([1]+list(map(int,input().split()))+[1])
        lr.append([1]+list(map(int,input().split()))+[1])
    lr.append([1 for _ in range(w+1)])
    ud.append([1 for _ in range(w+2)])

    q=deque()
    q.append([1,1])
    while q:
        x,y=q.popleft()
        if 0<=y-1 and lr[x][y-1]==0:
            if dist[x][y-1]==-1 or dist[x][y-1]>dist[x][y]+1:
                q.append([x,y-1])
                dist[x][y-1]=dist[x][y]+1
        if y+1<=w+1 and lr[x][y]==0:
            if dist[x][y+1]==-1 or dist[x][y+1]>dist[x][y]+1:
                q.append([x,y+1])
                dist[x][y+1]=dist[x][y]+1
        if 0<=x-1 and ud[x-1][y]==0:
            if dist[x-1][y]==-1 or dist[x-1][y]>dist[x][y]+1:
                q.append([x-1,y])
                dist[x-1][y]=dist[x][y]+1
        if x+1<=h+1 and ud[x][y]==0:
            if dist[x+1][y]==-1 or dist[x+1][y]>dist[x][y]+1:
                q.append([x+1,y])
                dist[x+1][y]=dist[x][y]+1
    if dist[h][w]==-1:
        ans.append(0)
    else:
        ans.append(dist[h][w])
for i in ans:
    print(i)

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



while True:
    W, H = map(int, input().split())
    if W == 0 and H == 0:
        break
    adj = defaultdict(list)
    for i in range(H):
        if i == 0:
            vertical = list(map(int, input().split()))
            for j in range(1, W):
                if vertical[j - 1] == 1:
                    continue
                adj[(i, j - 1)].append((i, j))
                adj[(i, j)].append((i, j - 1))
        else:
            horizontal = list(map(int, input().split()))
            for j in range(W):
                if horizontal[j] == 1:
                    continue
                adj[(i - 1, j)].append((i, j))
                adj[(i, j)].append((i - 1, j))

            vertical = list(map(int, input().split()))
            for j in range(1, W):
                if vertical[j - 1] == 1:
                    continue
                adj[(i, j - 1)].append((i, j))
                adj[(i, j)].append((i, j - 1))

    start = (0, 0)
    goal = (H - 1, W - 1)


    from collections import deque
    dist = [[-1] * W for _ in range(H)]
    q = deque([])
    sy, sx = start
    dist[sy][sx] = 1
    q.append(start)
    while len(q) > 0:
        v = q.popleft()
        y, x = v
        if v == goal:
            print(dist[y][x])
            break
        for u in adj[v]:
            ny, nx = u
            if dist[ny][nx] != -1:
                continue
            dist[ny][nx] = dist[y][x] + 1
            q.append(u)
    else:
        print(0)

Solution (Python):
from collections import deque
import sys
import copy


def input():
    return sys.stdin.readline()[:-1]


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

    if w == h == 0:
        exit(0)

    M = []
    for _ in range(h*2-1):
        tmp = input()
        if len(tmp) != w*2-1:
            tmp = tmp+' '
        M.append(list(tmp))
    check = copy.deepcopy(M)
    check[0][0] = '1'

    que = deque([])
    que.append((0, 0, 1))
    mv_list = [(1, 0, 2, 0), (-1, 0, -2, 0), (0, 1, 0, 2), (0, -1, 0, -2)]
    while True:
        if not(que):
            print(0)
            break

        nm = que.popleft()
        if nm[0] == (w*2-2) and nm[1] == (h*2-2):
            print(nm[2])
            break

        for mv in mv_list:
            x1 = nm[0] + mv[0]
            x2 = nm[0] + mv[2]
            y1 = nm[1] + mv[1]
            y2 = nm[1] + mv[3]
            if 0 <= x1 <= w*2-1 and 0 <= y1 <= h*2-1 and 0 <= x2 <= w*2-1 and 0 <= y2 <= h*2-1 and M[y1][x1] == '0' and check[y2][x2] == ' ':
                check[y2][x2] = ''
                que.append((x2, y2, nm[2]+1))

Solution (Python):
from collections import deque

def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 1
    while queue:
      
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return visited[y][x]
        r = ([1, 0, 0], [-1, 0, 1], [0, 1, 2], [0, -1, 3])
        for j, k, l in r:
          new_y, new_x = y+j, x+k 
          if (0 <= new_y < d) and (0 <= new_x < w):
            if visited[new_y][new_x] >= 10 ** 10:
              if (l == 0) and (maze[2 * y + 1][x] == 0):
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
              elif (l == 1) and (maze[2 * y - 1][x] == 0):
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
              elif (l == 2) and (maze[2 * y][x] == 0):
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
              elif (l == 3) and (maze[2 * y][x - 1] == 0):
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
                
                
T = True
while T:
  w, d = map(int, input().split())
  if (w, d) == (0, 0):
    T = False
    quit()
  visited = [[float("inf")] * w for i in range(d)]
  visited2 = [[0] * w for i in range(d)]
  visited[0][0] = 1
  visited2[0][0] = 1
  maze = [0] * (2 * d - 1)
  for i in range(2 * d - 1):
    maze[i] = list(map(int, input().split()))
  
  bfs(maze, visited, 0, 0, d - 1, w - 1)
  
  if visited[d - 1][w - 1] >= 10 ** 10:
    print(0)
  else:
    print(visited[d - 1][w - 1])

Solution (Python):
while(1):
    w, h = map(int, input().split())
    if not h+w:
        break
    h = 2*h-1
    w = 2*w-1
    m = [[1] * (w+2) for i in range(h+2)]
    for j in range(1, h+1):
        a = [int(i) for i in input().split()] 
        if j%2:
            m[j][1:w+1] = [0] * w
            for k in range(w//2):
                m[j][2*k+2] = a[k]
        else:
            for k in range(w-w//2):
                m[j][2*k+1] = a[k]

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

    s = [1, 1]
    d = [[-1 for k in range(w+2)] for j in range(h+2)]
    todo = [s]
    d[s[0]][s[1]] = 0
    while(todo != []):
        v = todo.pop(0)
        for k in range(4):
            if m[v[0]+dx[k]][v[1]+dy[k]] != 1 and d[v[0]+dx[k]][v[1]+dy[k]] == -1:
                d[v[0]+dx[k]][v[1]+dy[k]] = d[v[0]][v[1]]+1
                todo.append([v[0]+dx[k], v[1]+dy[k]])
    print(d[-2][-2]//2+1 if d[-2][-2] != -1 else 0)

Solution (Python):
import queue

def step(q, dist, i, j, ni, nj):
    if ni < 0 or ni >= h or nj < 0 or nj >= w: return q
    if dist[ni][nj] == -1:
        q.put((ni, nj))
        dist[ni][nj] = dist[i][j] + 1
    return q


def bfs():
    q = queue.Queue()
    q.put((0, 0))
    dist = [[-1] * w for _ in range(h)]
    dist[0][0] = 1
    while True:
        i, j = q.get()

        if left[i][j] == 0:
            ni, nj = i, j-1
            q = step(q, dist, i, j, ni, nj)
        
        if right[i][j] == 0:
            ni, nj = i, j+1
            q = step(q, dist, i, j, ni, nj)
        
        if up[i][j] == 0:
            ni, nj = i-1, j
            q = step(q, dist, i, j, ni, nj)

        if down[i][j] == 0:
            ni, nj = i+1, j
            q = step(q, dist, i, j, ni, nj)
    
        if q.empty(): break

    return dist[-1][-1]


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

    
    left = [[1] * w for _ in range(h)]
    right = [[1] * w for _ in range(h)]
    up = [[1] * w for _ in range(h)]
    down = [[1] * w for _ in range(h)]

    up[0][0] = 0
    down[-1][-1] = 0

    for i in range(2 * h - 1):
        line = list(map(int, input().split()))
        if i % 2 == 0:
            i2 = i // 2
            for j in range(0, w-1):
                right[i2][j] = line[j]
                left[i2][j+1] = line[j]
        else:
            i2 = i // 2
            for j in range(w):
                down[i2][j] = line[j]
                up[i2+1][j] = line[j]
    
    ans = bfs()
    print(ans if ans != -1 else 0)

Solution (Python):
from collections import deque


def main():
    ans = []
    while True:
        W, H = map(int, input().split())
        if W == 0 == H:
            break
        ipts = [input() if i % 2 == 1 else input()+" " for i in range(2*H-1)]
        v_wall = [[[False, False, False, False] for _ in range(W)] for _ in range(H)]
        for y in range(0, 2*H-1, 2):
            for x in range(0, 2*W-1, 2):
                for k in range(4):
                    dy, dx = moves[k]
                    ny, nx = y+dy, x+dx
                    if 0 <= ny < 2*H-1 and 0 <= nx < 2*W-1 and ipts[ny][nx] == "1":
                        v_wall[y//2][x//2][k] = True
        gd = 0
        que = deque([(0, 0, 1)])
        visited = set()
        visited.add((0, 0))
        while que:
            y, x, d = que.popleft()
            if y == H-1 and x == W-1:
                gd = d
                break
            for i in range(4):
                dy, dx = moves[i]
                ny, nx = y+dy, x+dx
                if 0 <= ny < H and 0 <= nx < W and not v_wall[y][x][i] and (ny, nx) not in visited:
                    que.append((ny, nx, d+1))
                    visited.add((ny, nx))
        ans.append(gd)
    for a in ans:
        print(a)


if __name__ == "__main__":
    moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    main()

Solution (Python):


import sys
from collections import deque

while True:
    W, H = map(int, sys.stdin.readline().strip().split())

    if (W == 0) and (H == 0):
        break

    Ph = []  
    Pv = []  

    for h in range(2 * H - 1):
        p = list(map(int, sys.stdin.readline().strip().split()))
        if h % 2 == 0:
            Ph.append(p)
        else:
            Pv.append(p)

    
    fp = [[True] * W for _ in range(H)]  

    q = deque()
    counter = 1
    q.append((0, 0, counter))
    fp[0][0] = False

    ans_counter = 0
    while q:
        flag = False
        ux, uy, counter = q.popleft()
        

        if (ux == W - 1) and (uy == H -1):
            ans_counter = counter
            break

        for i in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
            vx = ux + i[0]
            vy = uy + i[1]
            

            if (vx < 0) or (vx >= W):
                continue
            if (vy < 0) or (vy >= H):
                continue
            if fp[vy][vx] is False:
                continue
            

            if (i[1] == 1) and (Pv[uy][ux] == 0):  
                q.append((vx, vy, counter + 1))
                fp[vy][vx] = False
            elif (i[1] == -1) and (Pv[vy][ux] == 0):  
                q.append((vx, vy, counter + 1))
                fp[vy][vx] = False
            elif (i[0] == 1) and (Ph[uy][ux] == 0):  
                q.append((vx, vy, counter + 1))
                fp[vy][vx] = False
            elif (i[0] == -1) and (Ph[uy][vx] == 0):  
                q.append((vx, vy, counter + 1))
                fp[vy][vx] = False

    print(ans_counter)