トップ > AtCoder > ABC246E - Bishop 2

ABC246E - Bishop 2

AtCoder AtCoder-Beginner Contest グラフ グラフ-最短経路 グラフ-BFS グラフ-BFS-01BFS


【参考】最短経路問題 - 競プロはじめました

方法1

考え方

ダイクストラ法と同じように，最短距離が未確定の頂点のうち，最小のものから確定させて更新すれば良さそう．

1マスずつ動かす問題に帰着するにはどうすればよいか考える．直前の移動方向を覚えておけば

  • 直前の移動方向と同じ方向に動くなら，直前のマスと距離は変わらない
  • 別な方向に動くなら，直前のマスの距離＋１
と，1マスずつ動かす問題に帰着できる．よって，01BFSで解ける．

ただし，直前の移動方向（頂点に侵入する向き）は全て区別して覚えておく必要がある．例えば，最短となる方法が，2種類の「直前の移動方向」で実現できる場合，「直前の移動方向」の情報を一つに潰すことはできない．

そこで，どの方向から頂点に入るかを区別する（頂点の数を4倍にする）．

回答例

スタート地点は次ステップで必ず方向が変わるように初期化する．

from collections import deque
N = int(input())
Ax, Ay = map(lambda x:int(x) - 1, input().split())
Bx, By = map(lambda x:int(x) - 1, input().split())
board = [list(input()) for _ in range(N)]

dx = [-1, -1, 1, 1]
dy = [-1, 1, -1, 1]
INF = 1 << 60
dist = [[[INF] * 4 for _ in range(N)] for _ in range(N)]
dist[Ax][Ay] = [0] * 4

q = deque([(Ax, Ay, -1, 0)])
while q:
    x, y, dir, d = q.pop()
    if d > dist[x][y][dir]:
        continue
    for i in range(4):
        x2, y2 = x + dx[i], y + dy[i]
        if not (0 <= x2 < N and 0 <= y2 < N):
            continue
        if board[x2][y2] == '#':
            continue
        if dir == i and dist[x][y][dir] < dist[x2][y2][i]:
            dist[x2][y2][i] = dist[x][y][dir]
            q.append((x2, y2, i, dist[x2][y2][i]))
        elif dir != i and dist[x][y][dir] + 1 < dist[x2][y2][i]:
            dist[x2][y2][i] = dist[x][y][dir] + 1
            q.appendleft((x2, y2, i, dist[x2][y2][i]))

print(min(dist[Bx][By]) if min(dist[Bx][By]) < INF else -1)

方法2

考え方

1マスずつ考えるのではなく，ある頂点を取り出したときに進める範囲を全て探索する．こうすると，次のステップでは必ず方向が変わるので，どの向きで頂点に入るかの情報が不要になる．

よって，キューの前から入れる操作（コストゼロの場合の操作）はなくなり，後ろから入れる（コスト1の操作）だけになる．

探索の打ち切り方がポイント．自分の持っている値以下の頂点に出くわしたら，その頂点はその先の頂点の更新に関し，自分の役割を代替してくれる（過去/未来）．そのため，スキップして良い．

これは，次のようにも考えられる：更新しようとしている値より小さい値を持つ頂点より先は見なくて良い．そのような頂点から先は，すでにこれから更新する値よりも小さな値で更新されているか，その頂点自体がキューに入っていてこれから更新される（他の方向には更新されているが，今見ている方向には更新されていない可能性がある）かのどちらかであるため．そのマスを起点に更新させれば良い．
※更新しようとしている値と同じ値のマスは飛ばせない．その先のマスは，自分が更新したほうが（方向を変えなくて良いぶん）1小さくなるから．

Editorial - AtCoder Beginner Contest 246

回答例

from collections import deque
N = int(input())
Ax, Ay = map(lambda x:int(x) - 1, input().split())
Bx, By = map(lambda x:int(x) - 1, input().split())
board = [list(input()) for _ in range(N)]

dx = [-1, -1, 1, 1]
dy = [-1, 1, -1, 1]
INF = 1 << 60
dist = [[INF] * N for _ in range(N)]
dist[Ax][Ay] = 0

q = deque([(Ax, Ay)])
while q:
    x, y = q.popleft()
    for i in range(4):
        for j in range(1, N + 1):
            x2, y2 = x + j * dx[i], y + j * dy[i]
            if not (0 <= x2 < N and 0 <= y2 < N):
                break
            if board[x2][y2] == '#':
                break
            if dist[x][y] + 1 < dist[x2][y2]:
                dist[x2][y2] = dist[x][y] + 1
                q.append((x2, y2))
            elif dist[x2][y2] <= dist[x][y]:
                break

print(dist[Bx][By] if dist[Bx][By] < INF else -1)

【参考】Submission #30654721 - AtCoder Beginner Contest 246

参考

$K$が有限だと難しくなる．
F - Pond Skater

「ある頂点を取り出したときにコスト0で進める範囲を全て探索する」方法を使うと，全く同様に解ける．
ABC170F - Pond Skater - 競プロはじめました