With a proper observation, we can see that this problem is boiled down to a problem of counting the number of closed path consisting of walls and interior of the grid that splits \(S\) and \(G\).

• Here, a “closed path” is defined to be a loop that can be obtained by connecting \(8\)-adjacent walls. If there is \(S\) inside this loop and \(G\) outside the loop, then we cannot mutually travel between \(S\) and \(G\).

At a glance, the condition of “splits \(S\) and \(G\)” seems troublesome, but this can be computed in the following way.

First, let’s take an arbitrary path between \(S\) and \(G\). It is shown as red squares in the following figure.
Next, consider a set consisting of squares that can be reached from the upper side. It is shown as blue squares in the following figure. # is an example of closed path consisting of walls.

With red and blue squares, the condition of “splits \(S\) and \(G\)” can actually be rephrased as follows:

• The number of times that the closed path consisting of wall squares strides over the boundary of red and blue square is odd.

  • For example, in the figure above it strides over three times.

Once we know this fact, it can now be boiled down to a shortest path problem. That is, roughly speaking, for a square \((x, y)\) painted red, the following problem

• \(d_{i,j,f} :=\) the way and the number of ways of building walls that starts from \((x, y)\) and strides over the red-blue boundary \(f \pmod 2\) times, so that the distance to \((i, j)\) is the shortest

is nothing more than a shortest-path problem, and what we want to find is \(d_{x,y,1}\). (We omit the details. Beware of the treatment of boundary of the grid.)

The time complexity is \(\mathrm{O}(N^3)\). (The Constraint is probably loose enough to get AC for \(\mathrm{O}(N^3 \log N)\) too.)