この問題は、「縦移動と横移動を \(1\) 回ずつ交互に行う」という条件（＊）さえなければ単なるグリッド上の最短経路問題であり幅優先探索 (BFS) で解くことができますが、この条件が厄介です。そこで、この条件を別の条件に言い換えてみましょう。

上図のように、グリッドの各マスを市松模様に黒と白で塗ることを考えましょう。今、スタートマスが黒マスであり、最初（\(1\) 回目）の移動が縦移動であると仮定します。すると、

• 奇数回目の移動は縦移動、偶数回目の移動は横移動
• 移動経路によらず、偶数回の移動を行った後は黒マス上におり、奇数回の移動を行った後は白マス上にいる

ことから、

• 黒マスから白マスに移動する時は常に縦移動、白マスから黒マスに移動する時は常に横移動

であることが言え、逆にこれを満たす経路は条件（＊）を満たします。最初の移動が横移動である場合はこの逆（黒マスから白マスへの移動は横移動、白マスから黒マスへの移動は縦移動）になります。スタートマスが白マスである場合も同様です。

よって、本問題は以下のアルゴリズムで解くことができます。

1. 「黒マスから白マスへの移動は縦移動、白マスから黒マスへの移動は横移動」という条件の下でのスタートマスからゴールマスへの最短経路を求める。これは、グリッドの各マスを頂点集合、「各黒マスからその上下に隣接する白マスへの有向辺」と「各白マスからその左右に隣接する黒マスへの有向辺」を辺集合とした有向グラフ上での最短経路問題なので、BFS を用いればよい。
2. 同様に、「黒マスから白マスへの移動は横移動、白マスから黒マスへの移動は縦移動」という条件の下でのスタートマスからゴールマスへの最短経路を求める。
3. 1 と 2 の最小値を求めて出力する。

計算量は \(O(HW)\) です。

なお、本解説のような条件の言い換えを用いずとも、現在のマスと直前の移動方向のペアを状態と見て BFS することでも本問題を解くことができます（詳細略）。

実装例 (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;
}