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 position ~(r, c)~ using exactly ~D~ down movements, ~L~ left movements, and ~R~ 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.

Time Complexity: ~\mathcal O(N^5)~

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 ~(1, 1)~ to ~(N, N)~. Note that since Marcus is not allowed to travel up, he can never increase the number of down movements. He must travel down exactly ~N-1~ times, and thus ~D = N-1~ in every case. Now, we need to find the number of times Marcus moves left and right. Note that in the best case, Marcus moves exactly ~N-1~ 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 ~x~ units left, he must move exactly ~N-1+x~ units right. Observe that in the optimal solution, you should move left as little times as possible, as moving left increases both the ~L~ count and the ~R~ 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 ~D+L+R~). Since ~D = N-1, R = x, L = N-1+x~, we can show that ~dist[r][c] = N-1 + x + N-1 + x~. Rearranging this equation gives us ~x = \frac{dist[r][c]}{2} - (N-1)~, which in turn gives us the values we need: ~D, L, R~.

In the case that there is no valid path, we can use another BFS to check if position ~(N, N)~ is visited while beginning at position ~(1, 1)~.

Time Complexity: ~\mathcal O(N^2)~