Approach
Breadth-first search
For ABC224 D — 8 Puzzle on Graph, the implementation explores reachable states in layers, which is the standard shape for unweighted shortest paths and minimum-step transitions.
- Model each valid configuration as a state and each legal move as an edge.
- Seed the queue with the starting state and mark it immediately.
- Expand each state once, recording distance or reachability for unseen neighbours.
Code notes
- 62 lines of Python from the credited upstream file abc224_d.py.
- The implementation visibly relies on sequence storage, hash lookup, ordered lookup, work queue.
- No explicit loop blocks detected.
Complexity
Verify that each state and transition is processed only a bounded number of times; that determines the traversal cost.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
12 3 4def main():5 from collections import defaultdict, deque6 import sys7 8 input = sys.stdin.readline9 10 n = 911 m = int(input())12 graph = [[] for _ in range(n)]13 14 for _ in range(m):15 ai, bi = map(int, input().split())16 ai -= 117 bi -= 118 19 graph[ai].append(bi)20 graph[bi].append(ai)21 22 p = list(map(int, input().split()))23 empty = '8'24 pieces = [empty] * n25 26 for i, pi in enumerate(p):27 pi -= 128 pieces[pi] = str(i)29 30 pieces = ''.join(pieces)31 goal = '012345678'32 dist = defaultdict(int)33 dist[pieces] = 034 q = deque()35 q.append(pieces)36 37 while q:38 qi = q.popleft()39 di = dist[qi]40 41 for i in range(n):42 if str(qi[i]) != empty:43 continue44 45 for to in graph[i]:46 tmp = list(qi)47 tmp[i], tmp[to] = tmp[to], tmp[i]48 tmp = ''.join(tmp)49 50 if tmp not in dist.keys():51 dist[tmp] = di + 152 q.append(tmp)53 54 if goal not in dist.keys():55 print(-1)56 else:57 print(dist[goal])58 59 60if __name__ == "__main__":61 main()62