atcoder ABC176 D - Wizard in Mazeの勉強
・やったこと
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)