#include #include #include #include using namespace std; // 素数を求める関数 (エラトステネスの篩) vector sieve(int limit) { vector is_prime(limit + 1, true); is_prime[0] = is_prime[1] = false; for (int i = 2; i <= limit; i++) { if (is_prime[i]) { for (int j = i * i; j <= limit; j += i) { is_prime[j] = false; } } } vector primes; for (int i = 2; i <= limit; i++) { if (is_prime[i]) { primes.push_back(i); } } return primes; } struct State { int x, y, A, B, C, D; }; int bfs(int H, int W, const vector& grid, pair start, pair goal, const vector& primes) { // 4方向の移動 (右, 左, 下, 上) vector> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 最小移動回数を格納する配列 vector>> visited(H, vector>(W, vector(primes.size(), false))); // BFS のキュー (x, y, A, B, C, D の移動回数) queue q; q.push({start.first, start.second, 0, 0, 0, 0}); visited[start.first][start.second][0] = true; while (!q.empty()) { State current = q.front(); q.pop(); // ゴールに到達したら操作回数の合計を返す if (current.x == goal.first && current.y == goal.second) { return current.A + current.B + current.C + current.D; } // 4方向に対して素数回の移動を試す for (auto& dir : directions) { int nx = current.x + dir.first; int ny = current.y + dir.second; if (nx >= 0 && nx < H && ny >= 0 && ny < W && grid[nx][ny] != '#') { // 各方向に対して素数回の移動を試みる for (int i = 0; i < primes.size(); i++) { if (!visited[nx][ny][i]) { visited[nx][ny][i] = true; q.push({nx, ny, current.A + primes[i], current.B + primes[i], current.C + primes[i], current.D + primes[i]}); } } } } } return -1; // ゴールに到達できなかった場合 } int main() { int H, W; cin >> H >> W; vector grid(H); pair start, goal; for (int i = 0; i < H; i++) { cin >> grid[i]; for (int j = 0; j < W; j++) { if (grid[i][j] == 'S') { start = {i, j}; } else if (grid[i][j] == 'G') { goal = {i, j}; } } } // 最大移動回数は最大で40(HとWの最大値)なので、エラトステネスの篩で素数を計算 int max_move = max(H, W); vector primes = sieve(max_move * 2); // 最大で80回の移動をカバー // BFSによる探索 int result = bfs(H, W, grid, start, goal, primes); cout << result << endl; return 0; }