struct State {
    int row, col;         // Current position
    int direction;        // Current direction: 0=none, 1=up, 2=right, 3=down, 4=left
    int lastJumpLength;   // Length of the last jump
    int jumps;            // Number of jumps taken so far

    // Constructor
    State(int r, int c, int dir, int jumpLen, int j)
        : row(r), col(c), direction(dir), lastJumpLength(jumpLen), jumps(j) {}

    // Create a unique key for this state (used for visited set)
    std::string getKey() const {
        return std::to_string(row) + "," + std::to_string(col) + "," +
               std::to_string(direction) + "," + std::to_string(lastJumpLength);
    }
};

int getMinJumps(std::vector<std::string>& grid) {
    int n = grid.size();
    if (n == 0) return -1;
    int m = grid[0].size();

    // Find the start and end positions
    int startRow = -1, startCol = -1;
    int endRow = -1, endCol = -1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 'S') {
                startRow = i;
                startCol = j;
                // Replace 'S' with '*' to simplify checks
                grid[i][j] = '*';
            } else if (grid[i][j] == 'E') {
                endRow = i;
                endCol = j;
                // Replace 'E' with '*' to simplify checks
                grid[i][j] = '*';
            }
        }
    }

    // If start or end isn't found, return -1
    if (startRow == -1 || endRow == -1) {
        return -1;
    }

    // Directions: none, up, right, down, left
    const int dr[] = {0, -1, 0, 1, 0};
    const int dc[] = {0, 0, 1, 0, -1};

    // BFS queue
    std::queue<State> q;
    q.emplace(startRow, startCol, 0, 0, 0); // Start with no direction and 0 jumps

    // Keep track of visited states
    std::unordered_map<std::string, bool> visited;

    while (!q.empty()) {
        State current = q.front();
        q.pop();

        // Check if we've reached the end
        if (current.row == endRow && current.col == endCol) {
            return current.jumps;
        }

        // Skip if we've already visited this state
        std::string key = current.getKey();
        if (visited.find(key) != visited.end()) {
            continue;
        }
        visited[key] = true;

        // If we're in the middle of a multi-unit jump, we must continue in the same direction
        if (current.lastJumpLength > 1) {
            int dir = current.direction;
            for (int k = 1; k <= m + n; k++) { // Maximum jump length could be m+n (grid diagonal)
                int newRow = current.row + dr[dir] * k;
                int newCol = current.col + dc[dir] * k;

                // Check if the landing cell is valid and empty
                if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < m && grid[newRow][newCol] == '*') {
                    q.emplace(newRow, newCol, dir, k, current.jumps + 1);
                }
            }
        } else {
            // We can choose any direction
            for (int dir = 1; dir <= 4; dir++) {
                for (int k = 1; k <= m + n; k++) { // Maximum jump length could be m+n
                    int newRow = current.row + dr[dir] * k;
                    int newCol = current.col + dc[dir] * k;

                    // Check if the landing cell is valid and empty
                    if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < m && grid[newRow][newCol] == '*') {
                        q.emplace(newRow, newCol, dir, k, current.jumps + 1);
                    }
                }
            }
        }
    }

    // If we cannot reach the end
    return -1;
}