😸

[ABC213 E Stronger Takahashi] Queueを2個使ってBFS

2021/08/12に公開

Python

(問題ページ) ABC213 E Stronger Takahashi

私のやり方は、ちょっとイレギュラーかもしれません。(ACは、してます。計算量が少し抑えられ、Pythondで実行時間 343 msくらいになります)
間違ってたら誰か教えてくれると信じて・・・

1.考え方(塀の壊しかた)

「パンチを 1 回繰り出すことで任意の 2×2 の区画内の塀を壊して道にすることができます」
この条件を次のように処理します。

塀に遭遇した時に、その塀を壊すことにした場合を考えます。(コスト1増える)
すると、壊すことにした塀を含む2×2 の区画は、4通り考えられます。(パターン1～4)
つまり、「壊すことにした塀からは、その周りの8方向にコスト0で移動できる」と想定できます。
(移動先のコストが、現在地のコスト以下の場合は、移動しない)

2.全体の処理の流れ

Queueを2つ用意します。
queue1: 道のBFS用
queue2: 塀からの移動用

(1)まず、スタート地点からBFSを行い、道を通っていけるところ(コスト0)をすべて探索します。
このとき、塀に遭遇したらコスト+1し、その塀の位置をqueue2に追加します。
(ただし、移動先(塀)のコストが、現在地の"コスト+1"以下の場合は、移動しない)
(2)queue2に入っている塀に対し、そのまわり8方向へコスト0で移動し
移動先のアドレスをqueue1に追加します。
(移動先のコストが、現在地のコスト以下の場合は、移動しない)
(3) queue1、queue2が空になるまで、(1)(2)を繰返し

3.code

# -*- coding: utf-8 -*-
import sys
from collections import deque


def main():
    H,W = list(map(int, sys.stdin.readline().split()))
    S_list = [ ["B"]*(W+2) ] + \
             [ ["B"] + list(sys.stdin.readline().rstrip()) + ["B"] for _ in range(H) ] +\
             [ ["B"]*(W+2) ]


    INF = float("inf")
    dp = [ [INF]*len(S_list[0]) for _ in range(len(S_list)) ]

    delta1 = [(1,0), (-1,0), (0,1), (0,-1)]  # (row, column)
    queue1 = deque([(1,1)])  # for search
    dp[1][1] = 0

    queue2 = deque()  # border
    delta2 = [ [dr,dc] for dr in range(-1, 2) for dc in range(-1, 2) if not(dr == dc == 0) ]


    while queue1 or queue2:
        while queue1:
            r,c = queue1.popleft()

            for dr,dc in delta1:
                nr = r + dr
                nc = c + dc

                if (dp[r][c] < dp[nr][nc]) and (S_list[nr][nc] == "."):
                    dp[nr][nc] = dp[r][c]
                    queue1.append( (nr, nc) )
                elif ((dp[r][c] + 1) < dp[nr][nc]) and (S_list[nr][nc] == "#"):
                    dp[nr][nc] = dp[r][c] + 1
                    queue2.append( (nr, nc) )


        while queue2:
            r,c = queue2.popleft()

            for dr,dc in delta2:
                nr = r + dr
                nc = c + dc

                if (dp[r][c] < dp[nr][nc]) and (S_list[nr][nc] != "B"):
                        dp[nr][nc] = dp[r][c]
                        queue1.append( (nr, nc) )


    print( dp[H][W] )


if __name__ == "__main__":
    main()

1.考え方(塀の壊しかた)

2.全体の処理の流れ

3.code

Discussion