, 2019

Solution:

For convenience, we will center the grid on the origin of the coordinate plane and align the outer corners of the grid with the points $(\pm 1, \pm 1)$, so that $(-1,1)$ is the capital of Gondor and $(1,-1)$ is the capital of Mordor.

We will use casework on which nation the city at $(0,0)$ is part of. Assume that it belongs to Gondor. Then consider the sequence of cities at $(1,0)$, $(1,1)$, $(0,1)$. If one of these belongs to Mordor, then all of the previous cities belong to Mordor, since Mordor must be connected. So we have $4$ choices for which cities belong to Mordor. Note that this also makes all the other cities in the sequence connected to Gondor. Similarly, we have $4$ (independent) choices for the sequence of cities $(0,-1)$, $(-1,-1)$, $(-1,0)$. All of these choices keep $(0,0)$ connected to Gondor except the choice that assigns all cities in both sequences to Mordor. Putting this together, the answer is $2(4 \cdot 4-1)=30$.