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
ans = []
while True:
    w, h = [int(x) for x in input().split()]
    if w == 0 and h == 0: break
    maze = [[1 for _ in range(2 * w + 1)] for _ in range(2 * h + 1)]
    for y in range(1, 2 * h):
        if y % 2 == 1:
            maze[y][2 : 2 * w : 2] = [int(x) for x in input().split()]
            maze[y][1 : 2 * w : 2] = [0] * w
        else:
            maze[y][1 : 2 * w : 2] = [int(x) for x in input().split()]

    que = deque([(1, 1, 0)])
    while que:
        y, x, d = que.popleft()
        if (y, x) == (2 * h - 1, 2 * w - 1):
            ans.append(d + 1)
            break
        for dy, dx in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            wy = y + dy
            wx = x + dx
            if maze[wy][wx] == 1: continue 
            ny = y + 2 * dy
            nx = x + 2 * dx
            if maze[ny][nx] == 1: continue 
            maze[ny][nx] = 1 
            que.append((ny, nx, d + 1))
    else:
        ans.append(0)

for i in ans:
    print(i)

Solution (Python):
from collections import deque
from collections import defaultdict


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

    grid = defaultdict()

    raw_grid = []

    for _ in range(0,2*H-1):
        raw_grid.append(list(map(int, input().split())))

    for i in range(W):                           
        for j in range(1, 2 * H - 2, 2):
            p = int(i+W*(j-1)/2)
            q = int(i+W*(j+1)/2)
            grid[(p, q)] = raw_grid[j][i]
            grid[(q, p)] = grid[(p, q)]

    for j in range(0,2*H-1,2):                  
        for i in range(W-1):
            p = int(i+W*j/2)
            q = int(i+1+W*j/2)
            grid[(p, q)] = raw_grid[j][i]
            grid[(q, p)] = grid[(p, q)]

    for i in range(W):              
        grid[(i,i-W)] = 1
        grid[(i-W,i)] = 1
        grid[(W*(H-1)+i,W*H+i )] = 1
        grid[(W*H+i, W*(H-1)+i)] = 1
    for j in range(H):              
        grid[(W*j,W*j-1)] = 1
        grid[(W*j-1,W*j)] = 1


    move = [1,-1, W, -W]
    start = 0

    se = set([start]) 

    next_set = deque()
    next_set.append((start, 0))
    flg =False

    while next_set:    
        p, t = next_set.popleft()     
        for dx in move:
            q = p + dx
            if (q < 0 or q > W * H - 1):
                continue
            if grid[(p, q)] == 1 or q in se:
                continue
            if q == W*H-1:
                print(t + 2)
                flg = True
                break
            se.add(q)   
            next_set.append((q, t + 1))     
        if flg:
            break
    if not flg:
        print(0)

Solution (Python):
while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0:
        break
    ywalls = [[0]*w for _ in range(h)]
    xwalls = [[0]*w for _ in range(h)]
    for i in range(2*h-1):
        walls = map(int, input().split())
        if i%2==0:
            for j, ele in enumerate(walls):
                ywalls[i//2][j]=ele
        else:
            for j, ele in enumerate(walls):
                xwalls[i//2][j]=ele

    d = [[-1]*w for _ in range(h)]
    sx, sy = 0, 0
    gx, gy = w-1, h-1
    from collections import deque
    q = deque([])
    q.append((sx, sy))
    d[sx][sy] = 0

    while len(q)>0:
        cur = q.popleft()
        
        curx, cury = cur[0], cur[1]
        if curx==gx and cury==gy:
            break
        for dx in range(-1, 2):
            for dy in range(-1, 2):
                if (dx==0 and dy!=0) or (dx!=0 and dy==0):
                    nx, ny = curx+dx, cury+dy
                    if 0<=nx<w and 0<=ny<h and d[ny][nx]==-1:
                        tx, ty = curx, cury
                        if dx==-1:
                            tx -=1
                        elif dy==-1:
                            ty -=1
                        if dx!=0 and ywalls[ty][tx]==0:
                            q.append((nx, ny))
                            d[ny][nx] = d[cury][curx]+1
                        elif dy!=0 and xwalls[ty][tx]==0:
                            q.append((nx, ny))
                            d[ny][nx] = d[cury][curx]+1

    print(d[gy][gx]+1)

Solution (Python):
from collections import deque

def gset(c,r,w,f,g):
    for ri in range(r):
        for ci in range(c):

            if ci>0 and w[ri][ci-1]==0:
                g[ri][ci].append((ri,ci-1))

            if ci<c-1 and w[ri][ci]==0:
                g[ri][ci].append((ri,ci+1))
            if ri>0 and f[ri-1][ci]==0:
                g[ri][ci].append((ri-1,ci))
            if ri<r-1 and f[ri][ci]==0:
                g[ri][ci].append((ri+1,ci))   

def bfs(g):
    q=deque()
    q.append((0,0))

    parent=[[-1]*(c) for i in range(r)]
    parent[0][0]=0
    yn=""
    while q:

        sty,stx = q.popleft()
        for vy,vx in g[sty][stx]:
            if r-1==vy and c-1==vx:
                dist[vy][vx]=dist[sty][stx]+1
                yn="yes"
                break
            elif parent[vy][vx] !=-1:
                continue
            else:
                parent[vy][vx]=(sty,stx)
                q.append((vy,vx))
                dist[vy][vx]=dist[sty][stx]+1
        if yn=="yes":
            break

    if yn=="yes":
        print(dist[r-1][c-1]+1)
    else:
        print(0)


icnt=0
icase=0
while True:
    c,r=map(int,input().split())
    if c==0 and r==0:
        break
    else:
        w=[[0] *(c-1) for i in range(r)]
        f=[[0] *c for i in range(r-1)]
        dist=[[0] *c for i in range(r)]
        if icase==0:
            for i in range(r-1):
                w[i]=list(map(int,input().split()))
                f[i]=list(map(int,input().split()))
            w[r-1]=list(map(int,input().split()))
        elif icase==1:
            f= [[0, 1], [1, 0]]
            w= [[1], [0], [1]]
        elif icase==2:

            w[0]=" 1 1 0 1 0 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1"
            f[0]="0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
            w[1]=" 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1"
            f[1]="0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
            w[2]=" 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1"
            f[2]="0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
            w[3]=" 1 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 0 1"
            f[3]="0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
            w[4]=" 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 1 1 1 1 0 1 1"
            f[4]="0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
            w[5]=" 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1"
            f[5]="0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
            w[6]=" 0 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 1 1 0 1"
            f[6]="0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1"
            w[7]=" 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1"
            f[7]="0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
            w[8]=" 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 1 1 0 1"
            f[8]="0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1"
            w[9]=" 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1"
            f[9]="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 0"
            w[10]=" 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1"
            f[10]="0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
            w[11]=" 1 1 1 1 1 1 0 1 1 0 1 0 0 1 1 1 1 0 0 1 1 1 1 0 1"
            f[11]="0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
            w[12]=" 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1"
            f[12]="0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
            w[13]=" 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1"
            f[13]="0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
            w[14]=" 1 1 1 0 1 1 0 1 0 0 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1"
            f[14]="0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
            w[15]=" 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0"
            f[15]="0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
            w[16]=" 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 0 1"
            f[16]="0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
            w[17]=" 1 1 0 1 0 0 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1"
            f[17]="0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
            w[18]=" 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1"
            f[18]="0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
            w[19]=" 1 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1"
            f[19]="0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
            w[20]=" 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1"
            f[20]="0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
            w[21]=" 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1"
            f[21]="0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
            w[22]=" 0 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1"
            f[22]="0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
            w[23]=" 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 0"
            f[23]="0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
            w[24]=" 1 1 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1"
            f[24]="0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
            w[25]=" 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1"
            f[25]="0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0"
            w[26]=" 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0"
            f[26]="0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
            w[27]=" 1 0 1 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 1 1 0 1"
            f[27]="0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
            w[28]=" 1 1 0 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1"
            for i in range(r-1):
                w[i]=list(map(int,w[i].split()))
                f[i]=list(map(int,f[i].split()))
            w[r-1]=list(map(int,w[r-1].split()))
        elif icase==3:
            ff=open("D:\999atcoder\q100\q032\q032in.txt")
            ll=ff.readline()
            for i in range(r-1):
                ll=ff.readline()
                w[i]=list(map(int,ll.split()))
                ll=ff.readline()
                f[i]=list(map(int,ll.split()))
            ll=ff.readline()
            w[r-1]=list(map(int,ll.split()))
            ff.close()
            icnt+=1
            if icnt>1:
                break
        g=[[[] for j in range(c)] for i in range(r)]
        gset(c,r,w,f,g)
    

        
        bfs(g)

Solution (Python):
from collections import deque

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

    field = []
    for _ in range(2 * H - 1):
        row = list(input())
        if len(row) == 2 * W - 2:
            row.append(' ')
        field.append(row)

    gy = 2 * H - 2
    gx = 2 * W - 2

    queue = deque()
    queue.append((0, 0, 1))

    min_step = 0
    while len(queue) > 0:
        y, x, step = queue.popleft()
        if field[y][x] != ' ':
            continue
        else:
            field[y][x] = 'X'

        if y == gy and x == gx:
            min_step = step
            break

        for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            if 0 <= y + dy <= gy and 0 <= x + dx <= gx:
                if field[y + dy][x + dx] == '0':
                    queue.append((y + 2 * dy, x + 2 * dx, step + 1))

    print(min_step)

Solution (Python):
cin = open(0).read().strip().split('\n')

from collections import deque

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

cnt = 0
while True:
    w,h = map(int, cin[cnt].split(' '))
    if w==0 and h==0: break

    var = [list(map(int, a.strip().split(' '))) for a in cin[cnt+1:cnt+1+(2*h-1):2]]
    hor = [list(map(int, a.split(' '))) for a in cin[cnt+2:cnt+2+(2*h-3):2]]

    q = deque()
    dist = [[0 for _ in range(w)] for _ in range(h)]
    dist[0][0] = 1
    q.append((0,0))
    while q:
        ph,pw = q.popleft()
        for dyi, dxi in zip(dy, dx):
            if ph+dyi>=h or ph+dyi<0: continue
            if pw+dxi>=w or pw+dxi<0: continue
            if dist[ph+dyi][pw+dxi] != 0: continue
            if (dyi==1 and hor[ph][pw] == 1) or (dyi==-1 and hor[ph+dyi][pw] == 1): continue
            if (dxi==1 and var[ph][pw] == 1) or (dxi==-1 and var[ph][pw+dxi] == 1): continue
            q.append((ph+dyi,pw+dxi))
            dist[ph+dyi][pw+dxi] = dist[ph][pw]+1
    print(dist[h-1][w-1])
    cnt += 2*h

Solution (Python):
import sys, collections
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    while True:
        w, h = LI()
        if w==0 and h==0:
            break
        else:
            
            wall_h = []
            wall_v = []
            for i in range(h-1):
                wall_v.append(LI())
                wall_h.append(LI())
            wall_v.append(LI())
            
            
            
            
            
            

            que = collections.deque()
            que.append((0, 0))
            dist = [[INF]*w for _ in range(h)]
            dist[0][0] = 1
            while que:
                cy, cx = que.popleft()
                
                ny = cy
                nx = cx+1
                if 0<=ny<h and 0<=nx<w and wall_v[cy][cx]==0 and dist[ny][nx]>=INF:
                    que.append((ny, nx))
                    dist[ny][nx] = dist[cy][cx]+1
                
                ny = cy+1
                nx = cx
                if 0<=ny<h and 0<=nx<w and wall_h[cy][cx]==0 and dist[ny][nx]>=INF:
                    que.append((ny, nx))
                    dist[ny][nx] = dist[cy][cx]+1
                
                ny = cy
                nx = cx-1
                if 0<=ny<h and 0<=nx<w and wall_v[cy][cx-1]==0 and dist[ny][nx]>=INF:
                    que.append((ny, nx))
                    dist[ny][nx] = dist[cy][cx]+1
                
                ny = cy-1
                nx = cx
                if 0<=ny<h and 0<=nx<w and wall_h[cy-1][cx]==0 and dist[ny][nx]>=INF:
                    que.append((ny, nx))
                    dist[ny][nx] = dist[cy][cx]+1

        
        
        
        if dist[-1][-1]<INF:
            print(dist[-1][-1])
        else:
            print(0)
        


if __name__ == '__main__':
    resolve()

Solution (Python):
from collections import deque
dirc = ((-1, 0), (0, 1), (1, 0), (0, -1))
while 1:
    w, h = map(int, input().split())
    if w==0:
        break
    maze = [[[0]*4 for i in range(w)] for _ in range(h)]
    for idx in range(2*h-1):
        if idx%2==0:
            horizon = list(map(int, input().split()))
            for i, j in enumerate(horizon):
                if j==1:
                    maze[idx//2][i][1] = -1
                    maze[idx//2][i+1][3] = -1
        else:
            vertical = list(map(int, input().split()))
            for i, j in enumerate(vertical):
                if j==1:
                    maze[idx//2][i][2] = -1
                    maze[idx//2+1][i][0] = -1
    queue = deque()
    queue.appendleft((0, (0, 0)))
    checked = [[0]*w for _ in range(h)]
    ans = 0
    while queue:
        c, (y, x) = queue.pop()
        c += 1
        if checked[y][x]:
            continue
        checked[y][x] = 1
        if (y, x)==(h-1, w-1):
            ans = c
            break
        for i, (dy, dx) in enumerate(dirc):
            if maze[y][x][i]==-1:
                continue
            ny, nx = y+dy, x+dx
            if nx<0 or nx>=w or ny<0 or ny>=h:
                continue
            if not checked[ny][nx]:
                queue.appendleft((c, (ny, nx)))
    print(ans)

Solution (Python):
from collections import deque

while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0:
        break
    v_wall = [[0] * w for _ in range(h)]
    h_wall = [[0] * w for _ in range(h)]
    for i in range(2 * h - 1):
        walls = map(int, input().split())
        for j, obstacle in enumerate(walls):
            if i % 2 == 0:
                v_wall[i // 2][j] = obstacle
            else:
                h_wall[i // 2][j] = obstacle
    d = [[False] * w for _ in range(h)]
    que = deque()
    sx, sy = 0, 0
    gx, gy = w-1, h-1
    que.append((sx, sy))
    d[sy][sx] = 0

    while que:
        x, y = que.popleft()
        for dx, dy in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
            nx, ny = x + dx, y + dy
            
            if 0 <= nx < w and 0 <= ny < h and d[ny][nx] is False:
                if dy == 1:
                    if h_wall[y][x] == 0:
                        d[ny][nx] = d[y][x] + 1
                        que.append((nx, ny))
                elif dy == -1:
                    if h_wall[ny][nx] == 0:
                        d[ny][nx] = d[y][x] + 1
                        que.append((nx, ny))
                elif dx == 1:
                    if v_wall[y][x] == 0:
                        d[ny][nx] = d[y][x] + 1
                        que.append((nx, ny))
                elif dx == -1:
                    if v_wall[ny][nx] == 0:
                        d[ny][nx] = d[y][x] + 1
                        que.append((nx, ny))
    if d[gy][gx] is False:
        print(0)
    else:
        print(d[gy][gx] + 1)

Solution (Python):


def solve():
    import sys
    from collections import deque

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

        grid = []
        for i in range(H*2-1):
            _in = sys.stdin.readline().rstrip("\n")
            if i%2==0:
                _in += " "
            grid.append(list(_in))

        dist = [[0 for _ in range(W*2-1)] for __ in range(H*2-1)]
        dist[0][0] = 1
        que = deque([(0, 0)])

        while que:
            y, x = que.popleft()
            if grid[y][x] == "x": continue
            grid[y][x] = "x"

            if y==H*2-2 and x==W*2-2:
                
                break
            
            
            
            

            for ny, nx, direct in ((y-1,x,"up"), (y+1,x,"down"), (y,x-1,"left"), (y,x+1,"right")):
                if ny==-1 or ny==(H*2-1) or nx==-1 or nx==(W*2-1): continue
                if grid[ny][nx] != "0": continue
                if direct=="up" and grid[ny-1][nx]!="x":
                    dist[ny-1][nx] = dist[y][x] + 1
                    que.append((ny-1, nx))
                elif direct=="down" and grid[ny+1][nx]!="x":
                    dist[ny+1][nx] = dist[y][x] + 1
                    que.append((ny+1, nx))
                elif direct=="left" and grid[ny][nx-1]!="x":
                    dist[ny][nx-1] = dist[y][x] + 1
                    que.append((ny, nx-1))
                elif direct=="right" and grid[ny][nx+1]!="x":
                    dist[ny][nx+1] = dist[y][x] + 1
                    que.append((ny, nx+1))

        print(dist[H*2-2][W*2-2])


if __name__ == "__main__":
    solve()

Solution (Python):
from collections import deque

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

    if w == 0 and h == 0:
        break
    
    col = []
    row = []
    for i in range(2*h-1):
        if i % 2 == 0:
            col.append(list(map(int, input().split())))
        else:
            row.append(list(map(int, input().split())))
    
    dwdh = [(1, 0), (-1, 0), (0, 1), (0, -1)]

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

    que = deque([(0, 0)])
    d[0][0] = 1
    while que:
        qw, qh = que.popleft()

        for dw, dh in dwdh:
            nw = qw + dw
            nh = qh + dh
            if not(0 <= nh < h) or not(0 <= nw < w) or d[nh][nw]:
                continue
            if (dh == -1 and row[nh][nw] == 1) or (dh == 1 and row[nh-1][nw]==1):
                continue
            if (dw == -1 and col[nh][nw] == 1) or (dw == 1 and col[nh][nw-1] == 1):
                continue

            que.append((nw, nh))
            d[nh][nw] = d[qh][qw] + 1

    ans.append(d[h-1][w-1])

for a in ans:
    print(a)

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

    
    path = [[[True] * 4 for _ in range(w)] for _ in range(h)]
    for i in range(2 * h - 1):
        s = list(map(int, input().split()))
        x = i // 2

        if i % 2 == 0:
            for j in range(w-1):
                if s[j] == 1:
                    path[x][j][3] = False
                    path[x][j+1][2] = False
        else:
            for j in range(w):
                if s[j] == 1:
                    path[x][j][1] = False
                    path[x+1][j][0] = False

    from collections import deque
    que = deque()
    move = [(-1, 0, 0), (1, 0, 1), (0, -1, 2), (0, 1, 3)]
    inf = 10 ** 7
    d = [[inf] * w for _ in range(h)]
    que.append((0, 0))
    d[0][0] = 1

    while que:
        px, py = que.popleft()
        if px == h-1 and py == w-1:
            break
        for dx, dy, k in move:
            qx, qy = px + dx, py + dy
            if 0 <= qx < h and 0 <= qy < w \
                and path[px][py][k] == True and d[qx][qy] == inf:
                d[qx][qy] = d[px][py] + 1
                que.append((qx, qy))

    print(0 if d[h-1][w-1] == inf else d[h-1][w-1])

Solution (Python):
import collections,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
while 1:
    w,h = LI()
    if w==h==0:
        break
    hwall,wwall = [],[]
    for i in range(2*h-1):
        hwall.append(LI()) if i%2==0 else wwall.append(LI())
    dhdw = [[-1,0],[1,0],[0,-1],[0,1]]
    min_dist = [[-1]*w for _ in range(h)]
    seen = [[0]*w for _ in range(h)]
    queue = collections.deque() 
    def bfs():
        seen[0][0] = 1
        queue.append([0,0])
        min_dist[0][0] = 1
        while queue:
            qh,qw = queue.popleft()
            for dh,dw in dhdw:
                nh,nw = qh+dh,qw+dw
                if not(0<=nh<=h-1) or not(0<=nw<=w-1) or seen[nh][nw]:
                    continue
                if (dh==-1 and wwall[nh][nw]==1) or (dh==1 and wwall[nh-1][nw]==1):
                    continue
                if (dw==-1 and hwall[nh][nw]==1) or (dw==1 and hwall[nh][nw-1]==1):
                    continue
                if [nh,nw]==[h-1,w-1]:
                    return min_dist[qh][qw]+1
                seen[nh][nw] = 1
                queue.append([nh,nw])
                min_dist[nh][nw] = min_dist[qh][qw]+1
    print(bfs() or 0)

Solution (Python):

def get_direction(y,x,block):
    direction = []
    lr = block[y*2]
    if len(lr) > x and lr[x] == 0:
        direction.append((0,1))
    if 0 < x and lr[x-1] == 0:
        direction.append((0,-1))
    
    if y < H-1 and block[y*2+1][x] == 0:
        direction.append((1,0))
    
    if 0 < y and block[(y-1)*2+1][x] == 0:
        direction.append((-1,0))
    return direction

def bfs(block):
    field = [[0] * W for _ in range(H)]
    next_list = set()
    now_list = [(0,0)]
    cnt = 1
    while len(now_list) > 0:
        for _ in range(len(now_list)):
            y, x = now_list.pop()
            field[y][x] = 1
            
            direction = get_direction(y,x,block)
            for ny, nx in direction:
                ny += y
                nx += x
                if not (0 <= ny < H and 0 <= nx < W): continue
                if ny == H-1 and nx == W-1: return cnt+1
                if field[ny][nx] != 0: continue
                next_list.add((ny,nx))
        now_list = list(next_list)
        next_list = set()
        cnt += 1
    return 0

W, H = 0, 0
while True:
    W, H = map(int, input().split())
    if W+H == 0: break
    block = []
    for _ in range(H*2-1):
        block.append(list(map(int, input().split())))
    print(bfs(block))

Solution (Python):
from collections import deque
INF = float('INF')

while(1):
  w, h = map(int, input().split())
  if(w == 0 and h == 0):
    break
  wall = list() 
  for i in range(h*2-1):
    wall.append(list(map(int, input().split())))
  dist = [[INF] * w for _ in range(h)]
  dist[0][0] = 1
  q = deque([(0, 0)])
  while q:
    x, y = q.popleft()
    if(y >= 1): 
      if(dist[x][y-1] == INF):
        if(wall[x*2][y-1] == 0):
          dist[x][y-1] = dist[x][y] + 1
          q.append((x, y-1))
    if(y <= w-2): 
      if(dist[x][y+1] == INF):
        if(wall[x*2][y] == 0):
          dist[x][y+1] = dist[x][y] + 1
          q.append((x, y+1))
    if(x >= 1): 
      if(dist[x-1][y] == INF):
        if(wall[2*x-1][y] == 0):
          dist[x-1][y] = dist[x][y] + 1
          q.append((x-1, y))
    if(x <= h-2): 
      if(dist[x+1][y] == INF):
        if(wall[2*x+1][y] == 0):
          dist[x+1][y] = dist[x][y] + 1
          q.append((x+1, y))
    
  if(dist[h-1][w-1] == INF):
    print(0)
  else:
    print(dist[h-1][w-1])

Solution (Python):

from collections import deque
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    ans = []

    while True:
        w, h = map(int, readline().split())
        if (w, h) == (0, 0):
            break
        
        c = [[0]*(2 * w + 1) for _ in range(2 * h + 1)]
        for j in range(2 * w + 1):
            c[0][j] = 1
            c[2*h][j] = 1
        for i in range(1,2*h):
            c[i][0] = 1
            c[i][2*w] = 1
        for i, _ in enumerate(range(2 * h - 1)):
            if i % 2 == 0:
                S = [int(x) for x in readline().split()]
                for j, s in zip(range(2,2*w+1,2), S):
                    c[i+1][j] = s
            else:
                S = [int(x) for x in readline().split()]
                for j, s in zip(range(1,2*w+1,2), S):
                    c[i+1][j] = s
        
        seen = [[-1]*w for _ in range(h)]
        
        
        queue = deque([(0, 0)])
        seen[0][0] = 1
        possible = False
        while queue:
            x, y = queue.popleft()
            cx, cy = 2*x + 1, 2*y + 1
            if (x, y) == (h-1, w-1):
                possible = True
                ans.append(seen[x][y])
                break

            dx = [1, 0, -1, 0]
            dy = [0, 1, 0, -1]
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                ncx = cx + dx[i]
                ncy = cy + dy[i]
                
                if c[ncx][ncy] == 0 and seen[nx][ny] == -1:
                    seen[nx][ny] = seen[x][y] + 1
                    queue.append((nx, ny))

        if not possible:
            ans.append(0)
    
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()