Approach
Breadth-first search
For ABC246 E — Bishop 2, 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
- 55 lines of Python from the credited upstream file abc246_e.py.
- The implementation visibly relies on 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 deque6 import sys7 8 input = sys.stdin.readline9 10 n = int(input())11 12 sy, sx = map(int, input().split())13 ty, tx = map(int, input().split())14 sy -= 115 sx -= 116 ty -= 117 tx -= 118 s = [input().rstrip() for _ in range(n)]19 20 21 22 dxy = [(-1, -1), (1, 1), (1, -1), (-1, 1)]23 dist = [[-1] * n for _ in range(n)]24 dist[sy][sx] = 025 q = deque()26 q.append((sy, sx))27 28 while q:29 y, x = q.popleft()30 31 for dx, dy in dxy:32 ny = y + dy33 nx = x + dx34 35 while True:36 if nx < 0 or nx >= n or ny < 0 or ny >= n:37 break38 if s[ny][nx] == '#':39 break40 if dist[ny][nx] != -1 and dist[ny][nx] <= dist[y][x]:41 break42 43 if dist[ny][nx] < dist[y][x]:44 dist[ny][nx] = dist[y][x] + 145 q.append((ny, nx))46 47 ny += dy48 nx += dx49 50 print(dist[ty][tx])51 52 53if __name__ == "__main__":54 main()55