This subtask with n \le 10 can be solved by brute forcing all possible valid paths and then checking whether it is a palindrome. This gives \mathcal{O}(n 2^{2n-1}) time complexity.
This subtask has restriction of n \le 100. It can be solved using dp idea. We can iterate on palindrome, starting from left and right endings. Let dp state (x_1;y_1;x_2;y_2) be the state, that represent that we have matched x_1 + y_1 positions in palindrome and last positions are (x_1;y_1) and (x_2;y_2). We can go from state (x_1;y_1;x_2;y_2) to state (x'_1;y'_1;x'_2;y'_2) if and only if (x'_1;y'_1) can be reached from (x_1;y_1) in one valid step (in right or down direction) and (x'_2;y'_2) can be reached from (x_2;y_2) in one valid step (in left or up direction) and cells (x'_1;y'_1) and (x'_2;y'_2) are equal. This results in \mathcal{O}(n^4) time and memory complexity.
This subtask has restriction of n \le 500. It can be solved using the similar dp. However, it can be observed that there are a lot of unreachable states. We can optimize it using the fact that x_1 + y_1 + x_2 + y_2 = 2n-2, then y_2 = 2n-2 - x_1 - y_1 - x_2. Thus, we can make dp in \mathcal{O}(n^3) time complexity.
This subtask has restriction of n \le 1500. As the tests are generated randomly, we can check a big amount of paths and say that with big probability we have obtained correct answer. Let us observe all the paths that have |x_1-y_1| \le C and |x_2 - y_2| \le C, where is a constant. Now we can represent each dp state as (x_1;x_1-y_1+C;x_2;x_2-y_2+C) and do the same dp as in subtask , resulting in time complexity of \mathcal{O}(n^2C^2).
The last subtask does not have any additional restrictions. It can be solved optimizing the dp from subtask 4 using the same idea as we used to optimize dp from 2nd to 3rd subtask. We are interested in removing the biggest dimension, so we would be left with \mathcal{O}(n C^2) time complexity.
Setting C=50 would result in high enough probability to pass all test cases.
This is one of the solutions for this task. There could be a lot of more different solutions from this that would still pass the random tests.