CF413E Maze 2D

The last product of the R2 company in the 2D games' field is a new revolutionary algorithm of searching for the shortest path in a $ 2×n $ maze. Imagine a maze that looks like a $ 2×n $ rectangle, divided into unit squares. Each unit square is either an empty cell or an obstacle. In one unit of time, a person can move from an empty cell of the maze to any side-adjacent empty cell. The shortest path problem is formulated as follows. Given two free maze cells, you need to determine the minimum time required to go from one cell to the other. Unfortunately, the developed algorithm works well for only one request for finding the shortest path, in practice such requests occur quite often. You, as the chief R2 programmer, are commissioned to optimize the algorithm to find the shortest path. Write a program that will effectively respond to multiple requests to find the shortest path in a $ 2×n $ maze.

N/A

N/A