atcoder ABC176 D - Wizard in Mazeの勉強

atcoder.jp

・やったこと
atcoder ABC 213 E - Stronger Takahashiの勉強 - stosasa’s blogでやった問題と同じようにすれば解けるのでやってみた。0-1BFSで解ける。説明は下でコメントアウトしている。

from collections import deque
H,W=map(int,input().split())
sx,sy=map(int,input().split())
sx-=1
sy-=1
gx,gy=map(int,input().split())
gx-=1
gy-=1
field=[input() for _ in range(H)]

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

#魔法の回数がdist。大きい値で初期化
dist=[[10**18 for _ in range(W)] for _ in range(H)]

#スタートはdist=0、queにスタートを追加
dist[sx][sy]=0
que=deque()
que.append((sx,sy))

#0-1BFS
#queがからになるまで幅優先探索をやる
while len(que)!=0:
    x,y=que.popleft()  #queの先頭のペアを取り出す
  
  
  
    #普通の移動
    for i in range(4):
        next_x=x+dx[i]
        next_y=y+dy[i]
    
        #場外はスルー
        if next_x<0 or next_x>=H or next_y<0 or next_y>=W:
            continue
        #壁もスルー
        if field[next_x][next_y]=='#':
            continue
    
        #壁がないとき、queの前から。     
        if dist[next_x][next_y]>dist[x][y]:
            dist[next_x][next_y]=dist[x][y]
            que.appendleft((next_x,next_y))
        
        
        
    #魔法の移動
    for next_x in range(x-2,x+3):  #next_xはx-2からx+2まで動く.
        for next_y in range(y-2,y+3):
            
            if next_x<0 or next_x>=H or next_y<0 or next_y>=W:  #場外のとき
                continue
            
            if field[next_x][next_y]=='#':  #壁もスルー
                continue
            
            #前の座標のdist[x][y]+1(魔法のぶん+1する)のほうが次のよりも小さいとqueの後ろからいれる
            if dist[next_x][next_y]>dist[x][y]+1:
                dist[next_x][next_y]=dist[x][y]+1
                que.append((next_x,next_y))
      
print(dist[gx][gy] if dist[gx][gy]!=10**18 else -1)