Hmm just solved it, it's an interesting problem.

First of all rewrite the problem instead of going from 1,1 to n,n and then from n,n to 1,1 to you have to go from 1,1 to n,n twice.

I realized that this could be very easily solved with a DP in N^4 where you have x1,y1,x2,y2 where x1 and y1 correspond to the x and y coordinates of the first boy, and x2,y2 of the second boy. On every step of the DP you move both boys 1 square and since you know you move only right or left you will have 4 transitions (RR, RD, DR, DD).

Of course if you do this you will get TLE cause N=300, so you can optimize it to N^3 by realizing that you don't need to take into consideration both ys in the dp, since both boys move 1 square at the same time you can compress the DP by having a single number (I call it depth) which establishes how many steps both boys have done, therefore y=depth-x

Now you have a N^3 solution with N^3 memory, optimize it by reducing the dimension of the depth, instead of having every possible depth, only keep the last 2.

My solution: https://codeforces.me/contest/214/submission/46528198