Editorial for Back From Summer '19 P2: Straying From God's Light
Submitting an official solution before solving the problem yourself is a bannable offence.
For the first subtask, we can do five-dimensional Breadth First Search (BFS). We can use
dist[r][c][D][L][R] to be
1 if it is possible to move to posiiton using exactly down movements, left movements, and right movements, and
0 otherwise. The BFS is the classical BFS algorithm, except you should only check the down, left, and right directions, not up.
For the second subtask, we need a faster algorithm.
Let us assume, for now, that there is always at least one valid path from position to . Note that since Marcus is not allowed to travel up, he can never increase the number of down movements. He must travel down exactly times, and thus in every case. Now, we need to find the number times Marcus moves left and right. Note that in the best case, Marcus moves exactly times right, which is a constant. If Marcus moves one unit left, he must move an extra unit right later on to account for the change in the column. Thus, if Marcus moves units left, he must move exactly units right. Observe that in the optimal solution, you should move left as little times as possible, as moving left increases both the count and the count. Also, note that the cost to a position depends solely on the number of right movements.
Thus, to find the optimal solution, we can perform a Breadth First Search (BFS). Let
dist[r][c] represent the minimum number of movements in any direction (which is ). Since , we can show that . Rearranging this equation gives us , which in turn gives us the values we need: .
In the case that there is no valid path, we can use another BFS to check if position is visited while beginning at position .