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)$