Ускорить алгоритм : задача о лыжнике

@patyrocking · Регистрация: 28.05.2014

Студворк — интернет-сервис помощи студентам

Мене надо сделать програму для решения задачи. Скорость моего алгоритма нужно чуть-чуть поднять. Помогите, пожалуйста

Задача:
Лыжник начинает ехать по склону горы из (1;1). Едет в точку (N;M). Может двигаться только направо, вниз и по диагонали (вниз направо). На склоне расставлено K камней. Координаты камней записаны в массиве X. Вопрос - сколько всего есть путей для лыжника?

Я решил задачу бэктрекингом, но надо скорость чуточку поднять (для некоторых даных выполняется за 2,05 сек, а должно за 2). Спасибо за внимание

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
using namespace std;
 
unsigned short N, M, K;
unsigned short X[1000], Y[1000];
unsigned short ways = 0, i, x = 1, y = 1;
 
void recursion() {
    if(x == N && y == M) {
        ++ways;
        return;
    }
    for(i = 0; i < K; ++i)
        if(x == X[i] && y == Y[i])
            return;
    if(x < N) {
        ++x;
        recursion();
        if(y < M) {
            ++y;
            recursion();
            --y;
        }
        --x;
    }
    if(y < M) {
        ++y;
        recursion();
        --y;
    }
}
 
int main() {
    cin >> N;
    cin >> M;
    cin >> K;
 
    for(i = 0; i < K; ++i) {
        cin >> X[i];
        cin >> Y[i];
    }
    recursion();
    cout << ways;
}

@Shamil1 · 20.04.2018, 23:16

Создаёте двумерный массив N на M. Записываете в него местоположение всех камней. Для каждой диагонали, начиная с (2,1)-(1,2), для каждой клетки вычисляете, сколько маршрутов в неё ведёт (складывая значения в трёх клетках, из которых в неё можно попасть).

@patyrocking · 21.04.2018, 13:55 **[ТС]**

Переделал код как вы и предлагали. В массиве храню количество путей к точке. Нулями обозначены камни. Рекурсия проверяет доступность клеток. Ниже есть цикл для подсчета путей к точкам, используя числа в соседних точках. Скорость увеличилась до 0,002 секунды! Но есть проблема - тестер алгоритмов говорит, что мой алгоритм работает неверно для некоторых даных. Не могли бы вы глянуть есть ли тут ошибки? Еще подозрение, что некоректность связана з тем, что числа очень большие (для N=100, M=100) и просто происходит переполнение. Что думаете?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
using namespace std;
 
unsigned short N, M, K, rockX, rockY, x = 1, y = 1;
unsigned long long int MAP[101][101];
bool visit[101][101];
 
void recursion() {
    if(visit[x][y] || MAP[x][y] == 0 || x == N || y == M) return;
    visit[x][y] = true;
    ++x;
    recursion();
    ++y;
    recursion();
    --x;
    recursion();
    --y;
}
 
int main() {
    cin >> N;
    cin >> M;
    cin >> K;
    ++N;
    ++M;
 
    for(unsigned short i = 1; i < N; ++i)
        for(unsigned short j = 1; j < M; ++j) {
            MAP[i][j] = 1;
            visit[i][j] = false;
        }
 
    for(unsigned short i = 0; i < K; ++i) {
        cin >> rockX;
        cin >> rockY;
        MAP[rockX][rockY] = 0;
    }
 
    recursion();
 
    for(unsigned short i = 1; i < N; ++i)
        for(unsigned short j = 1; j < M; ++j)
            if(!visit[i][j])
                MAP[i][j] = 0;
 
    for(unsigned short i = 2; i < N; ++i)
        for(unsigned short j = 2; j < M; ++j)
            if(MAP[i][j] != 0)
                MAP[i][j] = MAP[i - 1][j] + MAP[i][j - 1] + MAP[i - 1][j - 1];
    for(unsigned short i = 1; i < M; ++i) {
        for(unsigned short j = 1; j < N; ++j)
            cout << MAP[j][M - i] << " ";
        cout << "\n";
    }
    cout << MAP[N - 1][M - 1];
}

@Shamil1 · 21.04.2018, 15:21

Сообщение от patyrocking

unsigned long long int

Вам нужны 256-битные числа. Используйте библиотеку или напишите сами. Вам понадобятся только операции сложения и деления на цифру (для преобразования в строку).

Сообщение от patyrocking

MAP[101][101]

Я бы динамически создавал массив N на M.

Сообщение от patyrocking

bool visit[101][101];

Этот массив не нужен.
Обход диагоналей можно сделать так:

C#
1
2
3
4
5
6
7
8
9
10
    for (int step = 1; step < n + m; step++)
    {
        var (row, col) = step < m ? (0, step) : (step - m + 1, m - 1);
        while (col >= 0 && row < m)
        {
            if (map[row, col] != 0)
                map[row, col] = count(row - 1, col) + count(row - 1, col - 1) + count(row, col - 1);
            (row, col) = (row + 1, col - 1);
        }
    }

Здесь step - номер диагонали, а функция count возвращает 0, если клетка за пределами поля или содержит камень.

Новые блоги и статьи Все статьи Все блоги /
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	Киев стоит - украинская песня zorxor 28.01.2026 wfWdiRqdTxc О Господи, Вечный, Ты . . . Я помоги, Бесконечный. . . Я прошу Ты. . . Я погибаю, спаси. . . Я прошу Тебя Вечный. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .
влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .

@Shamil1 Модератор 3134 / 2281 / 469 Регистрация: 26.03.2015 Сообщений: 8,877
	20.04.2018, 23:16
	Создаёте двумерный массив N на M. Записываете в него местоположение всех камней. Для каждой диагонали, начиная с (2,1)-(1,2), для каждой клетки вычисляете, сколько маршрутов в неё ведёт (складывая значения в трёх клетках, из которых в неё можно попасть). 1

Ускорить алгоритм : задача о лыжнике

Решение