Without the constraints that “horizontal and vertical moves should occur alternately” (*), this problem is merely a shortest path problem on a grid, and can be solved with a Breadth-First Search (BFS); the problem is that constraints themselves. Can we rephrase the condition in another way?

Consider painting the grid black and white alternately as the figure above. Suppose that the start square is a black square, and the first (\(1\)-st) move is a vertical move. Then,

• odd-indexed moves should be vertical, and even-indexed ones should be horizontal; and
• regardless of paths, you will be in a black square after an even number of moves, and in a white square after an odd number of moves.

Thus, we can say that

• when moving from a black square to a white square, you always move vertically; when moving from a white to black, you always move horizontally.

Conversely, such a path always satisfy the constraints (*). If the first move is a horizontal one, it is the other way round (move horizontally from black to white, and vertically from white to black). Same applies to the case where you start with a white square.

Thus, this problem can be solved with the following algorithm.

1. Find the shortest path subject to the condition that you move from black to white squares vertically, and from white to blacks squares horizontally. This is a shortest path problem on a graph whose vertex set is the cells in the grid, and edge set consists of directed edges from each black cell to vertically adjacent white cells, and from each white cell to horizontally adjacent white cells, so it can be solved with BFS.
2. Likewise, find the shortest path subject to the condition that you move from black to white squares horizontally, and from white to blacks squares vertically.
3. Find the smaller of 1. and 2., and print it.

The complexity is \(O(HW)\).

In fact, this problem can be solved without how we rephrased the problem in this editorial, but instead, treating the pair of the current cell and the previous direction of move as a state (details omitted).

Sample code (C++):

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9;

int main() {
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    for (int i = 0; i < h; i++) cin >> s[i];
    int si, sj, gi, gj;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (s[i][j] == 'S') {
                si = i, sj = j;
            } else if (s[i][j] == 'G') {
                gi = i, gj = j;
            }
        }
    }
    int ans = inf;
    vector<vector<pair<int, int>>> moves(2);
    moves[0] = {{0, 1},
                {0, -1}};
    moves[1] = {{1,  0},
                {-1, 0}};
    for (int p = 0; p < 2; p++) {
        vector d(h, vector<int>(w, inf));
        d[si][sj] = 0;
        queue<pair<int, int>> q;
        q.emplace(si, sj);
        while (!q.empty()) {
            auto [i, j] = q.front();
            q.pop();
            for (auto [di, dj]: moves[(i + j + p) & 1]) {
                int ni = i + di, nj = j + dj;
                if (ni < 0 or ni >= h or nj < 0 or nj >= w) continue;
                if (s[ni][nj] == '#') continue;
                if (d[ni][nj] == inf) {
                    d[ni][nj] = d[i][j] + 1;
                    q.emplace(ni, nj);
                }
            }
        }
        ans = min(ans, d[gi][gj]);
    }
    if (ans == inf) ans = -1;
    cout << ans << endl;
}