Почему мой код выдает ошибки, когда n = 1000?

Вопрос или проблема

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<vector<long int>> paths;

long int search(int x, int y){
    long int sum = 0;
    if (paths[x][y] >= 0) return paths[x][y];
    if (x + 1 < n){
        sum += search(x + 1, y);
    }
    if (y + 1 < n){
        sum += search(x, y + 1);
    }
    paths[x][y] = sum;
    return sum;
}

int main(){
    char s[1000];
    scanf("%i", &n);
    paths.resize(n);
    for (int i = 0; i < n; i++){
        scanf("%s", &s);
        int j = 1;
        for (auto c : s){
            if (c == '.'){
                paths[i].push_back(-1);
            }else{
                paths[i].push_back(0);
            }
        }
    }
    if (paths[n-1][n-1] < 0) paths[n-1][n-1] = 1;
    printf("%i\n", search(0, 0));
}

Ответ или решение

Ваша проблема с кодом, который приводит к ошибочным результатам при n = 1000, скорее всего, связана с несколькими критическими аспектами, включая инициализацию массива, переполнение целочисленных значений и использование рекурсии без достаточной проверки границ. Давайте более подробно разберем каждый из этих моментов.

1. Инициализация массива paths

В вашем коде вы используете paths как вектор векторов для хранения количества путей в каждой ячейке. Однако, при инициализации ячеек, вы используете push_back, что приводит к созданию вектора с нулевыми значениями, а не с инициализированными значениями (-1, если клетка проходима). Кроме того, массив paths должен быть определен изначально с фиксированным размером n и n, чтобы избежать неопределенного поведения.

2. Переполнение целочисленных значений

При вычислении количества путей вы используете тип long int, однако в процессе суммирования значений может произойти переполнение. Например, когда количество возможных путей слишком велико и выходит за пределы допустимого значения для типа long int. Это особенно важно, учитывая, что количество путей в сетке 1000×1000 может быть очень большим. Вам нужно использовать модуль 10^9 + 7 для предотвращения переполнения:

sum = (sum + search(x + 1, y)) % (1000000007);

3. Рекурсия и производительность

Ваш рекурсивный алгоритм может работать слишком медленно для больших значений n, так как он выполняет много повторяющихся вычислений. Вы можете оптимизировать этот процесс, используя динамическое программирование, чтобы избежать повторного подсчета количества путей для уже посещенных ячеек.

4. Недостаточная проверка границ

Убедитесь, что вы правильно проверяете выход за пределы массива. Также следует добавить проверку на наличие ловушек (трапов) в каждой ячейке перед продолжением поиска пути. Если текущая ячейка содержит ловушку, то необходимо вернуть 0, так как пути в этой ситуации недоступны.

Измененный код

Вот пример, как ваш код можно улучшить с учетом вышеупомянутых замечаний:

#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

const int MOD = 1000000007;
int n;
vector<vector<long long>> paths;

long long search(int x, int y) {
    if (x >= n || y >= n || paths[x][y] == 0) return 0;
    if (x == n-1 && y == n-1) return 1; // достигли цели
    if (paths[x][y] >= 0) return paths[x][y]; // уже вычислено

    long long sum = (search(x + 1, y) + search(x, y + 1)) % MOD;
    paths[x][y] = sum;
    return sum;
}

int main() {
    scanf("%i", &n);
    paths.assign(n, vector<long long>(n, -1));

    for (int i = 0; i < n; i++) {
        char s[1000];
        scanf("%s", s);
        for (int j = 0; j < n; j++) {
            if (s[j] == '*') {
                paths[i][j] = 0; // ловушка
            }
        }
    }

    printf("%lld\n", search(0, 0));
    return 0;
}

Заключение

Ваш код необходимо переписать с учетом указанных рекомендаций, чтобы избежать переполнения и улучшить производительность. Проверьте вводимые данные на наличие ловушек и убедитесь, что ваша логика обработки ячеек работает корректно для всех случаев. Использование динамического программирования вместо рекурсии может значительно ускорить выполнение и устранить проблемы с памятью на больших входах.