A safe has positions connected by one-way mechanical moves. Given the directed graph
of allowed moves, return the minimum number of moves to get from start to target, or
-1 if impossible.
safeCracking(graph, start, target)
Input format: edges | start | target, edges as a,b (directed a → b).
edges a,b b,c a,c, start a, target c // → 1 (a → c directly)
edges a,b b,c, start a, target c // → 2
edges a,b, start a, target z // → -1
Every move costs the same, and you want the fewest — the signature of an unweighted shortest-path problem, which BFS solves directly. The only twist versus undirected reachability: moves are one-way, an edge A→B doesn't imply B→A. That directionality affects how you generate neighbors, not which algorithm to use.
BFS explores in strict layers by distance: everything in one move, then two, never jumping ahead before the nearer layer finishes. The first time the target is dequeued, its distance is provably minimum — a shorter path would have surfaced in an earlier layer.
DFS might plunge down one long chain before trying a shorter direct route, reporting whatever distance it stumbles onto first — not necessarily minimal. That's why BFS, not DFS, is right whenever "fewest steps" is the goal on an unweighted graph.
Marking a node visited when enqueued, not when processed, prevents it from being added multiple times via different paths — wasted work, and potentially a longer route overwriting a shorter one already in flight. Since BFS processes in non-decreasing distance order, the first discovery of any node is always via a shortest path.
def safe_cracking(graph, start, target):
visited = {start}
queue = [(start, 0)]
while queue:
node, dist = queue.pop(0)
if node == target:
return dist
for nxt in graph.get(node, []):
if nxt not in visited:
visited.add(nxt)
queue.append((nxt, dist + 1))
return -1
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.