First, we'll make a few observations that will help us reduce the number of cases we need to analyse.
The walking distance between the squares (X1, Y1) and (X2, Y2) is at least abs(X2 - X1) + abs(Y2 - Y1), as that would be the distance in a grid with no holes. This obvious lower bound on the distance will be called "base distance" (of the squares).
In every game board, the distance between any square and each corner is precisely the base distance. This is obvious, as we can always take one step towards the corner (or, to be exact, towards one of the grid borders meeting in that corner).
Now, let's analyse the possible relative positions of Here and There. Consider the board divided into the thirds both horizontally and vertically into nine smaller squares (with the central one missing). If Here and There lie in the same smaller square, we can simply "zoom" into it and solve the same problem on a smaller game board. It's also clear from the previous observations that if the Here's smaller square and There's smaller square are not in the same third, neither horizontally nor vertically, their distance is precisely the base distance.
So, we're left with the only remaining case – when Here and There are in the same horizontal third of the board (the vertical case works the same way due to symmetry) but not in the same small square. Then, there are two subcases – either they are in the middle third, or in the upper/lower one.
If they are in the middle third, we can, without loss of generality, assume that Here is to the left from the hole (the removed smaller square in the centre) and There is to the right from it. Any way from Here to There needs to make a detour around the hole. There are essentially two choices – either the detour goes along the top border of the hole, or along the bottom one. In the "top" case, we start by moving from Here to the upper right corner of Here's smaller square (i.e. right next to the upper left corner of the hole). As we already observed, the travelled distance is the optimal one, as it is precisely the base distance. Then, we move up and slide along the upper border of the hole, until we reach its right end. Finally, we return back down, getting onto the upper left corner of There's square. Again, moving from this corner to There is optimal.
The detour we had to make consisted of moving up from Here, in order to reach the upper right corner of the the smaller square it is in and moving the same distance back from the upper left corner of There's square (and of two additional steps we had to make in order to move above the border of the hole and return back).
The other subcase, where we go along the bottom edge of the hole, works analogously, so we can simply pick the one which minimizes the detour we have to make.
Finally, if both Here and There are in the upper third of the board (again, the lower one works exactly the same), we divide it into three smaller horizontal stripes and repeat the same case-analysis on them. The only slightly different case is the one where both Here and There are in the middle third of the stripe – the check for the "is there a hole in between" condition is a tad more complicated.
In simple words, we are looking for the biggest hole between Here and There and, if there is one, we have to make a detour around it. This is performed by dividing the boards into three equal parts and seeing if Here and There are in the middle part. If they are not, we repeat the process again, otherwise we take the length of the necessary detour into consideration.
From the implementational point of view, it's easier to work with numbers in the interval 0, 3N-1, rather than 1, 3N.