まず、各空きマスが視線に入っているマスかどうかがわかっている時を考えます。その場合、問われている内容は「グリッドがあり、通れるマスと通れないマスがある時の \(S\) から \(G\) への最短路は？」といった最短路問題になります。そして、グリッド上の最短路問題は幅優先探索で \(\mathrm{O}(HW)\) で解くことができます。(グリッド上の最短路問題や幅優先探索(BFS) は ABC007 C に詳しいのでそちらも参考にしてください)

このような情報を踏まえると、元の問題は次のような方針で解けばよいことがわかります。

• はじめに、全ての空きマスについて視線に入っているかどうかを判定する。
• その後、前述の幅優先探索で \(S\), \(G\) 間の最短路を計算する。

1 番目の「全ての空きマスについて視線に入っているかどうかを判定」の方法を説明します。これは以下の手順で計算すればよいです。

• \(H\times W\) の 2 次元配列 viewed を、viewed[i][j] が 「マス \((i, j)\) が視線に入っている空きマスか？」を意味する 2 次元配列とする。viewed の要素ははじめ全て falseである。
• 全ての人に対して、その人の視線に入っているマスの viewed[i][j] を true にする。

上記のアルゴリズムは一見すると \(3\) 乗オーダー掛かるように見えますが、あるマスに視線を向ける人の人数は高々 4 人なので、全ての view[i][j] は最大でも 4 回しか true を代入されないことから、適切に実装すれば計算量が \(\mathrm{O}(HW)\) に抑えられるとわかります。

この部分の実装についても付記します。 人の向きは 4 種類ありますが、4種類全てを別々に実装すると実装量がかさばる上にバグの原因にもなるのでお勧めしません。そこで、コードを共通化することで本質部分の実装を 1 回で済ませる方法を以下で解説します。
はじめに 4 種類の人、およびその人が向いている方向を配列に格納します。(例えば下の例では、direction[0] は v で、 \((dx[0], dy[0]) = (1, 0)\) と対応している。ここで \(x\) は下方向, \(y\) は右方向)

  const string direction = "v>^<";
  const vector<int> dx{1, 0, -1, 0};
  const vector<int> dy{0, 1, 0, -1};

このような direction, dx, dy を用いて視線に入っているマスを調べることで、1 個の実装を 4 種類全ての判定に使い回すことができます。

  vector viewed(H, vector(W, 0));
  for (int k = 0; k < 4; k++) {
    for (int i = 0; i < H; i++) {
      for (int j = 0; j < W; j++) {
        if (g[i][j] != direction[k]) continue;
        int x = i, y = j;
        while (1) {
          x += dx[k], y += dy[k];
          if (!(0 <= x and x < H and 0 <= y and y < W) or g[x][y] != '.') break;
          viewed[x][y] = 1;
        }
      }
    }
  }

このように、共通化したコードを書くことによって、類似した計算が複数回登場するアルゴリズムの計算部分を 1 回の実装で済ませて実装量を減らすのは重要なテクニックです。E 問題を正確に通したい人は是非身に付けましょう。

C++ による実装例は次の通りです。

• 実装例 (C++)

#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>
using namespace std;

int main() {
  int H, W;
  cin >> H >> W;
  vector<string> g(H);
  for (auto& x : g) cin >> x;

  const vector<int> dx{1, 0, -1, 0};
  const vector<int> dy{0, 1, 0, -1};
  const string direction = "v>^<";
  auto in = [&](int h, int w) -> bool {
    return 0 <= h and h < H and 0 <= w and w < W;
  };
  auto is_obstacle = [&](char c) -> bool {
    return c == '#' or direction.find(c) != string::npos;
  };

  int Sh = -1, Sw = -1, Gh = -1, Gw = -1;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (g[i][j] == 'S') Sh = i, Sw = j;
      if (g[i][j] == 'G') Gh = i, Gw = j;
    }
  }

  vector viewed(H, vector(W, 0));
  for (int k = 0; k < 4; k++) {
    for (int i = 0; i < H; i++) {
      for (int j = 0; j < W; j++) {
        if (g[i][j] != direction[k]) continue;
        int x = i, y = j;
        while (1) {
          x += dx[k], y += dy[k];
          if (!in(x, y) or is_obstacle(g[x][y])) break;
          viewed[x][y] = 1;
        }
      }
    }
  }

  vector d(H, vector(W, -1));
  queue<pair<int, int>> Q;
  auto add = [&](int h, int w, int x) {
    if (d[h][w] == -1) d[h][w] = x, Q.emplace(h, w);
  };
  add(Sh, Sw, 0);
  while (!Q.empty()) {
    auto [h, w] = Q.front();
    Q.pop();
    for (int k = 0; k < 4; k++) {
      int x = h + dx[k];
      int y = w + dy[k];
      if (!in(x, y) or is_obstacle(g[x][y])) continue;
      if (viewed[x][y]) continue;
      add(x, y, d[h][w] + 1);
    }
  }
  cout << d[Gh][Gw] << endl;
}