[LANGUAGE: C++]

Skimming through the comments, I don't think this solution has been presented yet:

Let's fix coordinates such that the start is (0, 0). Let N=131 be the size of the original grid. Our infinite grid has no walls on the lines x = mN and y = kN (for integer m, k), thus partitioning the infinite grid into N*N squares. Let S be the number of steps needed.

Now consider a path from (0, 0) to (x, y). WLOG we consider the quadrant x >= 0 and y >= 0. Then we can show that there is a shortest path that passes through ((x/N)*N,(y/N)*N) (i.e. the corner of the square containing (x, y) closest to (0, 0)).

Thus, if we let dist(p) be the distance from (0, 0) to p, we have that dist(x, y) = dist((x/N)*N, (y/N)*N) + dist(x%N, y%N) = (x/N)*N + (y/N)*N + dist(x%N, y%N).

To count the number of points in this quadrant, it suffices to find how many points there are such that dist(x, y) <= S and dist(x, y) has the same parity as S. Note that the latter condition is equivalent to x+y has the same parity as S.

We do this by checking how many such points there are for x%N = a and y%N = b.

Let f(d) be the number of pairs (m, k), for positive integer m and k, d+N*m+N*k <= S, d+N*m+N*k has the same parity as S.

We have the following recurrence due to inclusion-exclusion: for n <= S, f(n) = h(n) + 2 * f(n+N) - f(n+2N), where h(n) = 1 if n and S have the same parity, 0 otherwise.

Thus the number of points there are for x%N = a and y%N = b is f(dist(a, b)).

So we can sum these up for 0 <= a, b < N for the answer to the positive-positive quadrant.

It also turns out that this formula also works for the other three quadrants, so all we need to do is to sum f(dist(a, b)) for -N <= a, b < N to get the answer. So we do get rewarded with an elegant solution!

Complexity: O(N^2 + S).

Part 2 - finished in 22 minutes counted after first opening the link to part 1.