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:
  w, h = list(map(int, input().split()))
  if w==0:
    break
  visited = [[0 for i in range(w)] for i in range(h)]
  visited[0][0] = 1
  ywall = [[] for i in range(h)]
  xwall = [[] for i in range(h-1)]
  for i in range(h*2-1):
    if i%2==0:
      ywall[i//2] = list(map(int, input().split()))
    else:
      xwall[i//2] = list(map(int, input().split()))
  gx, gy = w-1, h-1
  dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]
  que = deque([(0, 0)])
  while len(que):
    x, y = que.popleft()
    for dxt, dyt in zip(dx, dy):
      nx, ny = x+dxt, y+dyt
      if 0<=nx<w and 0<=ny<h:
        if visited[ny][nx]!=0:
          continue
        if (dxt==1 and ywall[y][x]!=1) or (dxt==-1 and ywall[y][x-1]!=1) or (dyt==1 and xwall[y][x]!=1) or (dyt==-1 and xwall[y-1][x]!=1):
          visited[ny][nx] = visited[y][x]+1
          que.append((nx, ny))
  print(visited[gy][gx])

Solution (Python):
from collections import deque

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


def bfs(w, h, m):
    cost = [[-1 for _ in range(w + (w - 1))] for _ in range(h + (h - 1))]
    
    que = deque()
    que.append([0, 0])
    cost[0][0] = 2
    while not len(que) == 0:
        p = que.popleft()
        
        if p[0] == 2 * h - 2 and p[1] == 2 * w - 2:
            return cost[p[0]][p[1]] // 2
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            
            if nx < 0 or ny < 0 or nx >= 2 * h - 1 or ny >= 2 * w - 1:
                
                continue
            if m[nx][ny] == -1:
                continue
            if not cost[nx][ny] == -1:
                continue
            
            cost[nx][ny] = cost[p[0]][p[1]] + 1
            
            que.append([nx, ny])
        
        
    return 0


if __name__ == "__main__":
    while True:
        W, H = map(int, input().split())
        if W == 0 and H == 0:
            break
        meizu = [[0 for _ in range(W + (W - 1))] for _ in range(H + (H - 1))]
        for i in range(2 * H - 1):
            kabe = list(map(int, input().split()))
            tmp = 0
            if i % 2 == 0:
                for j in range(len(meizu[i])):
                    if j % 2 == 1:
                        if kabe[tmp] == 1:
                            meizu[i][j] = -1
                        tmp += 1
            else:
                for j in range(len(meizu[i])):
                    if j % 2 == 0:
                        if kabe[tmp] == 1:
                            meizu[i][j] = -1
                        tmp += 1
        for i in range(len(meizu)):
            for j in range(len(meizu[i])):
                if i % 2 == 1 and j % 2 == 1:
                    meizu[i][j] = -1
        
        print(bfs(W, H, meizu))

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

        
        field = [[[0, 0, 0, 0, 0] for i in range(w)] for j in range(h)]

        for i in range(h * 2 - 1):
            wall = list(map(int, input().split()))
            y = i // 2
            
            if i % 2 == 0:
                for x in range(w - 1):
                    item = wall[x]
                    if item == 0:
                        field[y][x][2] = 1
                        field[y][x + 1][3] = 1

            
            else:
                for x in range(w):
                    item = wall[x]
                    if item == 0:
                        field[y][x][4] = 1
                        field[y + 1][x][1] = 1

        field[0][0][0] = 1

        i = 1
        while True:
            nextt = 0
            for y in range(h):
                for x in range(w):
                    if field[y][x][0] == i:
                        if field[y][x][1] == 1 and field[y - 1][x][0] == 0:
                            field[y - 1][x][0] = i + 1
                        if field[y][x][2] == 1 and field[y][x + 1][0] == 0:
                            field[y][x + 1][0] = i + 1
                        if field[y][x][3] == 1 and field[y][x - 1][0] == 0:
                            field[y][x - 1][0] = i + 1
                        if field[y][x][4] == 1 and field[y + 1][x][0] == 0:
                            field[y + 1][x][0] = i + 1

                        nextt += 1

                        if field[h - 1][w - 1][0] != 0:
                            print(i + 1)
                            nextt = -1
                            break
                if nextt == -1: break
            

            if nextt == -1: break
            if nextt == 0:
                print("0")
                break

            i += 1
        
                
main()

Solution (Python):
def explore(curlis,visited):
    global can
    if can==1 or curlis==[]:
        return
    i,j,k = curlis.pop(0)
    visited[i][j]=True
    if i == h-1 and j == w-1:
        print(k)
        visited.append("G")
        can=1
    for x,y in move:
        if check(i,j,x,y):
            visited[i+x][j+y]=True
            curlis.append([i+x,j+y,k+1])
    explore(curlis,visited)
		
		
def check(i,j,x,y):
    if 0<=i+x<h and 0<=j+y<w:
        if not visited[i+x][j+y]:
            if x==1:
                if orimap[2*i+1][j]:
                    return False
            if x==-1:
                if orimap[2*i-1][j]:
                    return False
            if y==1:
                if orimap[2*i][j]:
                    return False
            if y==-1:
                if orimap[2*i][j-1]:
                    return False
            return True
    return False

import sys
sys.setrecursionlimit(10000000)
move = ((0,1),(1,0),(-1,0),(0,-1))
w,h = map(int,input().split())
while w!=0 and h!=0:
    can=0
    orimap = []
    visited = []
    for _ in range((h*2)-1):
        if _ % 2==0:
            orimap.append(list(map(int,input().split()))+[1])
            visited.append([False]*w)
        elif _ % 2==1:
            orimap.append(list(map(int,input().split())))
    orimap.append([1]*w)
    explore([[0,0,1]],visited)
    if not can:
        print(0)
    w,h=map(int,input().split())

Solution (Python):

import queue
w,h=map(int,input().split())
while w!=0 or h!=0:
    
    maps=[]
    for i in range(h*2-1):
        k=list(map(int,input().split()))
        maps.append(k)
    
    
    def check(x,y,x2,y2):
        global maps
        if x2<0 or x2>=w or y2<0 or y2>=h:
            return False
        if x==x2:
            if maps[y+y2][x]!=0:
                return False
        if y==y2:
            if maps[y*2][(x+x2)//2]!=0:
                return False
        return True

    def bfs():
        
        q=queue.Queue()
        
        rawmap=[[0]*h for i in range(w)]
        
        dx=[1,0,-1,0]
        dy=[0,1,0,-1]
        
        q.put([0,0])
        rawmap[0][0]=1
        
        while q.qsize():
            
            x,y=q.get()
            if x==w-1 and y==h-1:
                break
            for i in range(4):
                x2=x+dx[i]
                y2=y+dy[i]
                if check(x,y,x2,y2) and rawmap[x2][y2]==0:
                    q.put([x2,y2])
                    rawmap[x2][y2]=rawmap[x][y]+1
        return rawmap[w-1][h-1]
        
    print(bfs())
    w,h=map(int,input().split())

Solution (Python):
while 1:
    w,h=map(int,input().split())
    if w==h==0:break
    maze,wall=[[float("inf") for i in range(w)] for j in range(h)],[]
    maze[0][0]=1
    for i in range(2*h-1):wall.append(list(map(int,input().split())))
    flag=0
    step=0
    while 1:
        if flag==1:break
        flag=1
        step+=1
        for i in range(w):
            for j in range(h):
                if maze[j][i]==step:
                    if i-1>=0 and wall[j*2][i-1]==0 and maze[j][i-1]>step+1:
                        maze[j][i-1],flag=step+1,0
                    if i+1<w and wall[j*2][i]==0 and maze[j][i+1]>step+1:
                        maze[j][i+1],flag=step+1,0
                    if j-1>=0 and wall[j*2-1][i]==0 and maze[j-1][i]>step+1:
                        maze[j-1][i],flag=step+1,0
                    if j+1<h and wall[j*2+1][i]==0 and maze[j+1][i]>step+1:
                        maze[j+1][i],flag=step+1,0
        if maze[-1][-1]!=float("inf"):break
    if maze[-1][-1]==float("inf"):print(0)
    else:print(maze[-1][-1])

Solution (Python):
from collections import deque

while True:
    w, h = map(int, input().split())
    if w == 0:
        break
    lr_walls = []
    ud_walls = []
    for i in range(2 * h - 1):
        wall = list(map(int, input().split()))
        if i % 2 == 0:
            lr_walls.append(wall)
        else:
            ud_walls.append(wall)
    checked = [[False] * w for _ in range(h)]
    checked[0][0] = True
    que = deque()
    que.append((1, 0, 0))
    while que:
        score, x, y = que.popleft()
        if (x, y) == (w - 1, h - 1):
            print(score)
            break

        if x < w - 1 and lr_walls[y][x] == 0 and not checked[y][x + 1]:
            checked[y][x + 1] = True
            que.append((score + 1, x + 1, y))

        if x > 0 and lr_walls[y][x - 1] == 0 and not checked[y][x - 1]:
            checked[y][x - 1] = True
            que.append((score + 1, x - 1, y))

        if y < h - 1 and ud_walls[y][x] == 0 and not checked[y + 1][x]:
            checked[y + 1][x] = True
            que.append((score + 1, x, y + 1))

        if y > 0 and ud_walls[y - 1][x] == 0 and not checked[y - 1][x]:
            checked[y - 1][x] = True
            que.append((score + 1, x, y - 1))
    else:
        print(0)

Solution (Python):

import queue
while 1:
    w,h=map(int,input().split())
    if w==0:
        break
    field=[[0 for i in range(w*2-1)] for i in range(h*2-1)]
    dist=[[0 for i in range(w*2-1)] for i in range(h*2-1)]
    for i in range(h*2-1):
        if i%2==0:
            s=input().split()
            for j in range(len(s)):
                if s[j]=='1':
                    field[i][1+j*2]=1
    
        else:
            s=input().split()
            for j in range(len(s)):
                if s[j]=='1':
                    field[i][j*2]=1
    s=(0,0)
    g=(h*2-2,w*2-2)
    q=queue.Queue()
    q.put(s)
    while not q.empty():
        y,x=q.get()
        if g==(y,x):
            print(dist[g[0]][g[1]]+1)
            break
        if 0<=y+1<h*2-1 and 0<=x<w*2-1 and field[y+1][x]!=1 and dist[y+2][x]==0:
            dist[y+2][x]=dist[y][x]+1
            q.put((y+2,x))
        if 0<=y-1<h*2-1 and 0<=x<w*2-1 and field[y-1][x]!=1 and dist[y-2][x]==0:
            dist[y-2][x]=dist[y][x]+1
            q.put((y-2,x))
        if 0<=y<h*2-1 and 0<=x+1<w*2-1 and field[y][x+1]!=1 and dist[y][x+2]==0:
            dist[y][x+2]=dist[y][x]+1
            q.put((y,x+2))
        if 0<=y<h*2-1 and 0<=x-1<w*2-1 and field[y][x-1]!=1 and dist[y][x-2]==0:
            dist[y][x-2]=dist[y][x]+1
            q.put((y,x-2))
    else:
        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)