atcoder ABC 213 E - Stronger Takahashiの勉強

DFS,BFS atcoder

atcoder.jp

・参考
AtCoder ABC 213 E - Stronger Takahashi (水色, 500 点) - けんちょんの競プロ精進記録

・やったこと
　参考記事をpythonで書いて実装した。パンチすることによって2*2のマスに移動できるのでそれをコスト1、通常の移動をコスト0として0-1BFSをして、実装する。注意点として、パンチしての移動は四隅に行くことができないことに注意。

・備考　
　提出の際はPyPyで提出してください。pythonだとTLEします。

from collections import deque
H,W=map(int,input().split())
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[0][0]=0
que=deque()
que.append((0,0))

#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 abs(next_x-x)+abs(next_y-y)==4:  #四隅はいけない
                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)
      
print(dist[H-1][W-1])

・類題
atcoder.jp