First, assume that we know whether each square is in a person’s line of sight. In this case, you are asked to solve the shortest distance from \(S\) to \(G\) on the grid, in which some squares are passable and some are not. A shortest path problem on a grid can be solved in a total of \(\mathrm{O}(HW)\) time with Breadth-First Search (BFS). (For more details on a shortest-path problem on a grid and BFS, see also ABC007 C (only in Japanese) that features the theme.)

Therefore, it turns out that this problem can be solved by the following approach.

• First, determine if each empty square is in a person’s sight.
• Then, perform a BFS as described above to find the shortest path from \(S\) to \(G\).

We now describe the first point: how to determine if each empty square is in a person’s sight? It can be computed as follows.

• Let viewed be a \((H\times W)\) two-dimensional array representing whether square \((i, j)\) is in a person’s sight. Initially, all elements of viewed are false.
• For each person, iterate the squares \((i,j)\) in that person’s sight to let viewed[i][j] be true.

At a glance, the algorithm above seems in a cubic order; however, any square is seen by at most people, so view[i][j] is set to true at most four times. Thus, the complexity is in fact bounded by \(\mathrm{O}(HW)\) with an appropriate implementation.

We will also mention the implementation here. While a person may face in one of the four directions, implementing them requires a heavy implementation and also bares more chance of bugs. Instead, we describe how to extract the implementation into a common code.
First, we declare arrays corresponding to people facing in each direction. (For instance, in the following code, direction[0] is v and corresponds to \((dx[0], dy[0]) = (1, 0)\), where \(x\) points down and \(y\) points right.)

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

By inspecting the squares in a person’s sight using such direction, dx, dy, we can use a single portion of implementation to all four kinds of directions.

  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;
        }
      }
    }
  }

In summary, it is an important technique to commonlize code to reduce implementation by writing multiple occurrences of similar computation as a single portion of implementation. If you want more accuracy on Problem E, do learn this technique.

A sample code in C++ follows.

• Sample code (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;
}