Treat each open cell as a node with up to four edges to its side neighbours. Every edge has the same cost, so breadth-first search is enough: it expands cells in rings of increasing distance from S, which means the first time a cell is reached, that distance is already the minimum. The reference keeps a dict steps from cell to distance and a frontier list for the current ring; building the next ring from the current one avoids a deque entirely. A cell enters steps the moment it is discovered, so it is never queued twice. The answer is steps.get(E, -1). Each cell is processed once and checks four neighbours, so time and memory are O(R x C) for an R by C grid.

Knowing the length is not enough to rebuild the route under a fixed tie-break. The clean trick is to run the same BFS from E instead, labelling every reachable cell with its distance to the end. From S, any neighbour whose label is exactly one smaller lies on some shortest path. Python compares lists of tuples cell by cell, so to get the smallest path you only need the smallest valid next cell at each step. The reference lists neighbours in the order up, left, right, down, which is already ascending (row, col) order, and takes the first that qualifies. That greedy walk can never strand you, because a cell with label d always has a neighbour labelled d - 1. Cost stays O(R x C).

With a battery, arriving at a cell is not the whole story: getting there with more charge left opens moves that a weaker arrival cannot make. So the search node becomes (cell, charge). From a node with charge >= 1, each open neighbour costs one unit, except that landing on C resets the charge to capacity. A node with 0 charge is a dead end and is simply not expanded. The visited set holds the full pair, so the same cell can be queued once per distinct charge level, which is what lets a detour through a charger beat a direct path that runs dry. BFS still applies because every move costs one. There are at most R x C x (capacity + 1) states, which bounds both time and memory.

On an endless plane BFS has no natural stopping point, so an enclosed end would loop forever. The fix is a finite search window. Take the smallest box containing start, end and every blocked point, and grow it by one cell on each side. Outside the original box there are no obstacles, and the added ring is entirely open, so any route that wanders further out can be pressed back onto that ring without getting longer. That means BFS restricted to the grown box finds the true shortest distance, and it finishes because the box is finite. The reference checks bounds and blocked for each neighbour and returns -1 when the frontier empties. Cost is proportional to the area of the box.