[BOJ 1697]かくれんぼ(Python)

8656 ワード
白駿 BFS テキストリンク

質問する


https://www.acmicpc.net/problem/1697

秀彬はどうやって瞬時に移動したのか...🙂🙃🙂
スビンの位置から1秒後に移動できる3つの経路をチェックするので,この問題は容易に解決できる.

問題を解く


アクセス関数をグラフで表します.
アクセスした数値をキー値とし、valueは1です.
  • 1秒後に移動可能な経路[n-1, n+1, 2 * n]location変数への割当て.
  • queue locationの要素を分離し、経過時間とともに入れる.
    ➣ for l in location: queue.append([l,sec])
  • キューからポップアップされた移動経路をチェックnum経過時間secnumアクセスせず、一定範囲内でのみチェック
    3-1. num到着地点の場合、以前は別ルートで来ていた場合がある可能性がありますが、より小さい値をmin_num変数に入れます.
    3-2. 非到達点ではnumのアクセスチェックを行い,移動可能な3つの経路を考慮する.
    3つのパスのうち、特定の範囲内にあり、アクセスされていないパスをキューに追加します.
    • 出力
  • min_num

    • コード#コード#

    import sys
from collections import deque
input = sys.stdin.readline

MIN_NUM = 100003
n, k = map(int,input().rstrip().rsplit())
location, sec = [n-1, n+1, 2 * n] , 1
visit = {}

queue = deque()
for l in location:
    queue.append([l,sec])

if n==k:
    print(0)
    sys.exit()

while(queue):
    num, sec = queue.popleft()

    if 0 <= num and num < 100003 and visit.get(num) is None:
        if num == k:
            MIN_NUM = min(sec,MIN_NUM)
        else:
            visit[num] = 1
            if 0 <= num-1 < 100003:
                if visit.get(num-1) is None:
                    queue.append([num-1,sec+1])
            if 0 <= num+1 < 100003:
                if visit.get(num+1) is None:
                    queue.append([num+1,sec+1])
            if 0 <= num*2 < 100003:
                if visit.get(num*2) is None:
                    queue.append([num*2,sec+1])

print(MIN_NUM)
    スレッド同期コンポーネント
    [moin-review] 2021-11-19