Consider we go from top left to the bottom right. Given a 50 * 50 board, the min step k is 98. If during our traversal, for each left or up turn the final answer increases by 2: 1 to go left/up, and 1 to go right/down to cancel that

The key mistake I made during contest is that I didn’t pay attention to k <= 1000 constraint!!!

Now how to construct k = 1000 path on a 50 * 50 board? We can create a zig-zag pattern, the maximal zig-zag pattern gives k > 1000 already!

Proof

1. every 4 rows, we make c left turns, i.e., increase the k by 2 * c

2. For a 50 row board, we will have  (50 / 4) * 2 * c, i.e., the final k is around 25 * (c = 50) = 1250 

3. Thus, we can satify our k = 1000 constraint

Note that for each left/up we take out, we reduce k by 2, i.e., we have a way to construct all paths with even k in [100, 1000]

Now what if k is odd number between [99, 999]? By our proof, we just need to change c to an odd number, e.g., 49, so that the maximal k is odd, and by our “reduction by 2” rule, we can construct all odd k >= 99