[伯俊13913]-鬼ごっこ(4)

💡質問する

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

💡に答える

既存のかくれんぼでは,逆追跡の問題のみが増加した.
bfsではかなり簡単であるが,2つの方法で解いた.
1つは優先キューデータ構造を用いたBFSである.
もう1つはキューデータ構造+BFS+再帰である.
答え方は以下の通りです.
優先キュー+BFSの使用
1.heapqに保存:(時間、現在位置、[今まで行った場所])
2.pop値が示す現在位置が目標点と同じかどうかを比較し続け、bfsを実行する.
キュー+BFS+再帰
1.bfsですが、dpを2次元配列として作成し、前回アクセスした場所を保存します.
2.同様にbfsを実行します.
3.現在位置が目標点と同じ場合は、再帰的に逆トレースを実行します.

💡コード#コード#

1番コード

import heapq

def bfs(now, target):
    if now == target:
        return 0, [now]
    elif now > target:
        return now - target, [i for i in range(now, target - 1, -1)]
    else:
        heapq.heappush(q, [0, now, [now]])
        while q:
            cnt, pos, trace = heapq.heappop(q)
            for i in [pos * 2, pos - 1, pos + 1]:
                if i == target:
                    return cnt + 1, trace + [i]
                if 0 <= i <= 100000 and not dp[i]:
                    dp[i] = True
                    heapq.heappush(q, [cnt + 1, i, trace + [i]])

if __name__ == "__main__":
    N, K = map(int,input().split())
    dp = [False] * (100000 + 1)
    q = []
    res, trace = bfs(N, K)
    print(res)
    print(*trace)

2番コード

from collections import deque
import sys
def check(now, target, res):
    if now == target:
        return res[::-1]
    else:
        res.append(dp[target][1])
        return check(now, dp[target][1], res)


def bfs(now, target):
    if now == target:
        return 0, [now]
    elif now > target:
        return now - target, [i for i in range(now, target - 1, -1)]
    else:
        dp[now][0] = 0
        while q:
            pos = q.popleft()
            for i in [pos * 2, pos + 1, pos -1]:
                if dp[target][0] != -1:
                    return dp[target][0], check(now, target, [target])
                    break
                if 0 <= i <= 100000 and dp[i][0] == -1:
                    dp[i][0] = dp[pos][0] + 1
                    dp[i][1] = pos
                    q.append(i)

if __name__ == "__main__":
    sys.setrecursionlimit(10000)
    N, K = map(int, input().split())
    dp = [[-1,-1] for _ in range(100001)]
    q = deque()
    q.append(N)
    res1, res2 = bfs(N, K)
    print(res1)
    print(*res2)

結果

結論として,第2の方法は時間的複雑さの面でより有効である.
個人的にも満足のいく質問です.
結果は以下の通りです.
1号メソッド結果

2号メソッド結果