Segfault task

[jhonspapa_2]

I’m trying to solve the SEGFAULT code below, but I don’t understand how to solve this problem. Maybe someone has solved it and can help me.

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct Position {
    int x;
    int y;
    int dist;

    Position(int _x, int _y, int _dist) : x(_x), y(_y), dist(_dist) {}
};

int captureMemory(int N, int M, vector<vector<char>>& RAM, int startX, int startY) {
    vector<vector<bool>> visited(N, vector<bool>(M, false));
    int count = 0;
    queue<Position> q;

    q.push(Position(startX, startY, 0));
    visited[startX][startY] = true;

    while (!q.empty()) {
        Position curr = q.front();
        q.pop();
        int x = curr.x;
        int y = curr.y;
        int dist = curr.dist;

        if (RAM[x][y] != '#' && RAM[x][y] != 'S') {
            RAM[x][y] = 'P';
            count++;
        }

        if (x > 0 && !visited[x - 1][y] && RAM[x - 1][y] != '#' && RAM[x - 1][y] != 'N') {
            q.push(Position(x - 1, y, dist + 1));
            visited[x - 1][y] = true;
        }
        if (x < N - 1 && !visited[x + 1][y] && RAM[x + 1][y] != '#' && RAM[x + 1][y] != 'N') {
            q.push(Position(x + 1, y, dist + 1));
            visited[x + 1][y] = true;
        }
        if (y > 0 && !visited[x][y - 1] && RAM[x][y - 1] != '#' && RAM[x][y - 1] != 'N') {
            q.push(Position(x, y - 1, dist + 1));
            visited[x][y - 1] = true;
        }
        if (y < M - 1 && !visited[x][y + 1] && RAM[x][y + 1] != '#' && RAM[x][y + 1] != 'N') {
            q.push(Position(x, y + 1, dist + 1));
            visited[x][y + 1] = true;
        }
    }

    return count;
}

int main() {
    int N, M;
    cin >> N >> M;

    vector<vector<char>> RAM(N, vector<char>(M));
    int startX, startY;

    for (int i = 0; i < N; i++) {
        string row;
        cin >> row;
        for (int j = 0; j < M; j++) {
            RAM[i][j] = row[j];
            if (RAM[i][j] == 'S') {
                startX = i;
                startY = j;
            }
        }
    }

    int K;
    cin >> K;

    vector<pair<pair<int, int>, char>> programs(K);

    for (int i = 0; i < K; i++) {
        int x, y;
        char dir;
        cin >> x >> y >> dir;
        programs[i] = make_pair(make_pair(x, y), dir);
    }

    for (const auto& program : programs) {
        int x = program.first.first;
        int y = program.first.second;
        char dir = program.second;

        while (x >= 0 && x < N && y >= 0 && y < M && RAM[x][y] != '#' && RAM[x][y] != 'S' && RAM[x][y] != 'N') {
            RAM[x][y] = 'N';
            if (dir == 'U') {
                x--;
            } else if (dir == 'D') {
                x++;
            } else if (dir == 'L') {
                y--;
            } else if (dir == 'R') {
                y++;
            }
        }
    }

    int capturedMemory = captureMemory(N, M, RAM, startX, startY);
    cout << capturedMemory << endl;

    return 0;
}

[simes]

I’ve not solved this, so I’m talking from a position of ignorance.

I’ve just tried a simulation, but get TLE every time. Perhaps there’s a better way?

[tjm]

The simulation per se should be fine. There is a small trap in the problem, since the upper bound for one of parameters is much larger than others (consider what would be the worst case scenario and how to improve runtime in that case).