Approach
Breadth-first search
For ABC289 E — Swap Places, 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
- 67 lines of Python from the credited upstream file abc289_e.py.
- The implementation visibly relies on sequence storage, 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 4from collections import deque5 6 7def solve():8 n, m = map(int, input().split())9 colors = list(map(int, input().split()))10 graph = [[] for _ in range(n)]11 12 for _ in range(m):13 ai, bi = map(int, input().split())14 ai -= 115 bi -= 116 17 graph[ai].append(bi)18 graph[bi].append(ai)19 20 21 22 q = deque()23 inf = 10 ** 1224 dist = [[inf for _ in range(n)] for _ in range(n)]25 26 def push(i, j, d):27 if dist[i][j] != inf:28 return29 30 dist[i][j] = d31 q.append((i, j))32 33 push(0, n - 1, 0)34 35 while q:36 a, b = q.popleft()37 di = dist[a][b]38 39 for na in graph[a]:40 for nb in graph[b]:41 if colors[na] == colors[nb]:42 continue43 44 push(na, nb, di + 1)45 46 ans = dist[n - 1][0]47 48 if ans == inf:49 ans = -150 51 print(ans)52 53 54def main():55 import sys56 57 input = sys.stdin.readline58 59 t = int(input())60 61 for _ in range(t):62 solve()63 64 65if __name__ == "__main__":66 main()67