Problem p02579 (python)

Fixed submission:
from collections import deque

def make_wall(maze,h,w):
    maze=deque(maze)
    for i in range(h):
        maze[i]="##"+maze[i]+"##"
    maze.appendleft("#"*(w+4))
    maze.appendleft("#"*(w+4))
    maze.append("#"*(w+4))
    maze.append("#"*(w+4))
    return list(maze)

def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    cost[sy][sx]=0
    walk = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    warp = [(i,j) for i in range(-2,3) for j in range(-2,3) if (i,j) not in [(0,0)]+walk]
    
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return cost[y][x]
        
        # 移動A
        for i,j in walk:
            ny, nx = y+i, x+j
            if maze[ny][nx] == "." and cost[ny][nx]>cost[y][x]:
                cost[ny][nx]=cost[y][x]
                queue.appendleft([ny,nx])
            
        # 移動B
        for i, j in warp:
            ny, nx = y+i, x+j
            if cost[ny][nx] > cost[y][x]+1 and maze[ny][nx]==".":
                cost[ny][nx]=cost[y][x]+1
                queue.append([ny,nx])
            
    return -1 #ゴールできない

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())

maze=[input() for _ in range(h)]

maze=make_wall(maze,h,w)
h+=4
w+=4
sy+=2
sx+=2
gy+=2
gx+=2

INF = 10**12
cost = [[INF]*w for _ in range(h)]

ans=bfs(maze, cost, sy-1, sx-1, gy-1, gx-1)
if ans==INF:
    ans=-1
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque

def make_wall(maze,h,w):
    maze=deque(maze)
    for i in range(h):
        maze[i]="##"+maze[i]+"##"
    maze.appendleft("#"*(w+4))
    maze.appendleft("#"*(w+4))
    maze.append("#"*(w+4))
    maze.append("#"*(w+4))
    return list(maze)

def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    cost[sy][sx]=0
    walk = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    warp = [(i,j) for i in range(-2,3) for j in range(-2,3) if (i,j) not in [(0,0)]+walk]
    
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return cost[y][x]
        
        # 移動A
        for i,j in walk:
            ny, nx = y+i, x+j
            if maze[ny][nx] == "." and cost[ny][nx]>cost[x][y]:
                cost[ny][nx]=cost[y][x]
                queue.appendleft([ny,nx])
            
        # 移動B
        for i, j in warp:
            ny, nx = y+i, x+j
            if cost[ny][nx] > cost[y][x]+1 and maze[ny][nx]==".":
                cost[ny][nx]=cost[y][x]+1
                queue.append([ny,nx])
            
    return -1 #ゴールできない

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())

maze=[input() for _ in range(h)]

maze=make_wall(maze,h,w)
h+=4
w+=4
sy+=2
sx+=2
gy+=2
gx+=2

INF = 10**12
cost = [[INF]*w for _ in range(h)]

ans=bfs(maze, cost, sy-1, sx-1, gy-1, gx-1)
if ans==INF:
    ans=-1
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque

def make_wall(maze,h,w):
    maze=deque(maze)
    for i in range(h):
        maze[i]="##"+maze[i]+"##"
    maze.appendleft("#"*(w+4))
    maze.appendleft("#"*(w+4))
    maze.append("#"*(w+4))
    maze.append("#"*(w+4))
    return list(maze)

def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    cost[sy][sx]=0
    walk = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    warp = [(i,j) for i in range(-2,3) for j in range(-2,3) if (i,j) not in [(0,0)]+walk]
    
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return cost[y][x]
        
        # 移動A
        for j, k in walk:
            ny, nx = y+j, x+k
            if maze[ny][nx] == "." and cost[ny][nx]>cost[x][y]:
                cost[ny][nx]=cost[x][y]
                queue.appendleft([ny,nx])
            
        # 移動B
        for ii, jj in warp:
            ny, nx = y+ii, x+jj
            if cost[y+ii][x+jj] > cost[y][x]+1 and maze[y+ii][x+jj]==".":
                cost[y+ii][x+jj]=cost[y][x]+1
                queue.append([y+ii,x+jj])
            
    return -1 #ゴールできない

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())

maze=[input() for _ in range(h)]

maze=make_wall(maze,h,w)
h+=4
w+=4
sy+=2
sx+=2
gy+=2
gx+=2

INF = 10**12
cost = [[INF]*w for _ in range(h)]
ans=bfs(maze, cost, sy-1, sx-1, gy-1, gx-1)
if ans==INF:
    ans=-1
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque

def make_wall(maze,h,w):
    maze=deque(maze)
    for i in range(h):
        maze[i]="##"+maze[i]+"##"
    maze.appendleft("#"*(w+4))
    maze.appendleft("#"*(w+4))
    maze.append("#"*(w+4))
    maze.append("#"*(w+4))
    return list(maze)

def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    warp[sy][sx]=0 #ワープ回数
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return warp[y][x]
        
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]): #進める方向
            ny, nx = y+j, x+k
            
            # 移動先候補が壁のとき
            if maze[ny][nx] == "#":
                for ii in range(-2,3):
                    for jj in range(-2,3):
                        # ワープする
                        if warp[y+ii][x+jj] > warp[y][x]+1 and maze[y+ii][x+jj]==".":
                            warp[y+ii][x+jj]=warp[y][x]+1
                            queue.append([y+ii,x+jj])
                
            if maze[ny][nx] == "." and warp[ny][nx]>warp[x][y]:
                warp[ny][nx]=warp[x][y]
                queue.appendleft([ny,nx])
            
    return -1 #ゴールできない

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())

maze=[input() for _ in range(h)]

maze=make_wall(maze,h,w)
h+=4
w+=4
sy+=2
sx+=2
gy+=2
gx+=2

INF = 10**12
warp = [[INF]*w for _ in range(h)]
ans=bfs(maze, warp, sy-1, sx-1, gy-1, gx-1)
if ans==INF:
    ans=-1
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque

def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    warp[sy][sx]=0 #ワープ回数
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return warp[y][x]
        
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]): #進める方向
            ny, nx = y+j, x+k
            
            # 迷路の範囲外なら戻る
            if ny < 0 or ny >= h or nx < 0 or nx >= w:
                continue
            
            # 移動先候補が壁のとき
            if maze[ny][nx] == "#":
                for ii in range(-2,3):
                    for jj in range(-2,3):
                        # 範囲外なら戻る
                        if y+ii<0 or y+ii>=h or x+jj<0 or x+jj>=w:
                            continue
                        # ワープする
                        if warp[y+ii][x+jj] > warp[y][x]+1 and maze[y+ii][x+jj]==".":
                            warp[y+ii][x+jj]=warp[y][x]+1
                            queue.append([y+ii,x+jj])
                
            if maze[ny][nx] == "." and warp[ny][nx]>warp[x][y]:
                warp[ny][nx]=warp[x][y]
                queue.appendleft([ny,nx])
            
    return -1 #ゴールできない

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())

maze=[input() for _ in range(h)]

INF = 10**12
warp = [[INF]*w for _ in range(h)]
ans=bfs(maze, warp, sy-1, sx-1, gy-1, gx-1)
if ans==INF:
    ans=-1
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque

def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    warp[sy][sx]=0 #ワープ回数
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return warp[y][x]
        
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]): #進める方向
            ny, nx = y+j, x+k
            
            # 迷路の範囲外なら戻る
            if ny < 0 or ny >= h or nx < 0 or nx >= w:
                continue
            
            # 移動先候補が壁のとき
            if maze[ny][nx] == "#":
                for ii in range(-2,3):
                    for jj in range(-2,3):
                        # 範囲外なら戻る
                        if y+ii<0 or y+ii>=h or x+jj<0 or x+jj>=w:
                            continue
                        # 移動先が通路かつ現状必要ワープ回数が多い
                        if warp[y+ii][x+jj] > warp[y][x]+1 and maze[y+ii][x+jj]==".":
                            warp[y+ii][x+jj]=warp[y][x]+1
                            queue.append([y+ii,x+jj])
                
            if maze[ny][nx] == "." and warp[ny][nx]>warp[x][y]:
                warp[ny][nx]=warp[x][y]
                queue.appendleft([ny,nx])
            
    return -1 #ゴールできない

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())

maze=[input() for _ in range(h)]

visited = [[-1]*w for _ in range(h)]
warp = [[10000]*w for _ in range(h)]
ans=bfs(maze, visited, sy-1, sx-1, gy-1, gx-1)
if ans==10000:
    ans=-1
print(ans)