Форум программистов, компьютерный форум CyberForum.ru

Не работает рекурсивная функция - C++

Восстановить пароль Регистрация
 
Епифан
0 / 0 / 0
Регистрация: 10.11.2016
Сообщений: 2
10.11.2016, 13:12     Не работает рекурсивная функция #1
У меня есть поле 80 на 80 клеток, с препятствиями. Функция должна в отдельный массив записавыть в соответствующую клеточку число, означающее, за сколько ходов туда можно добраться из начальных координат. Если в if приписать && n<3, то она работает, но в маленьком радиусе, если больше тройки число поставить, то уже не работает, никак не могу понять, в чем дело.

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
void search(int x, int y, int n) 
    {
        
    if (x>-1 && x<80 && y>-1 && y<80 && gg[x][y]==0)
    {
        int h;
        h=n+1;
        if(x-1>-1 && x-1<80 && (gg[x-1][y]==0 || qq[x-1][y]>n))
        {
            qq[x-1][y]=n;
            search(x-1,y,h);
        }
        if(x+1>-1 && x+1<80 && (gg[x+1][y]==0 || qq[x+1][y]>n))
        {
            qq[x+1][y]=n;
            search(x+1,y,h);
        }
        if(y+1>-1 && y+1<80 && (gg[x][y+1]==0 || qq[x][y+1]>n))
        {
            qq[x][y+1]=n;
            search(x,y+1,h);
        }
        if(y-1>-1 && y-1<80 && (gg[x][y-1]==0 || qq[x][y-1]>n))
        {
            qq[x][y-1]=n;
            search(x,y-1,h);
        }
    }
    }
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.11.2016, 13:12     Не работает рекурсивная функция
Посмотрите здесь:

C++ Рекурсивная функция
Рекурсивная функция C++
C++ рекурсивная функция
Рекурсивная функция C++
C++ Рекурсивная функция y=3x+5
C++ рекурсивная функция
Объяснить как работает рекурсивная функция и стек вызовов на моем примере C++
Как работает рекурсивная функция C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Archi0
28 / 14 / 4
Регистрация: 18.07.2013
Сообщений: 164
10.11.2016, 17:14     Не работает рекурсивная функция #2
Алгоритм Дейкстры. У вас каждая вершина графа связана с 4 соседними или меньше, если есть препятствия. И цена шага везде 1.

Добавлено через 26 минут
Единственно можно немного упростить, можно убрать проверку на сумму длин, потому что он равен шагу алгоритма (из-за того, что все ребра 1), а каждый посещенный узел отмечается флагом out уже на следующем шаге. Алгоритм завершает работу когда не остаётся узлов помеченных как visited и при этом не помеченных как out (иначе говоря цикл идет по узлам visited, но только по тем которые не получили флаг out в самом начале все флаги сброшены и только у стартовой точки visited). Могут остаться узлы не помеченные как visited, если препятствия их окружили, для того, чтобы отличать их от стартовой точки, стоит назначить параметру длина пути некоторое начальное значение -1 например, а стартовая точка 0 будет.

Добавлено через 4 минуты
вместо флага visited можно сравнивать значение поля с шагом цикла, а out тогда значение меньше этого шага. (упрощение которое следует опять из-за того, что все ребра 1)

Добавлено через 5 минут
Для того чтобы не бегать по всему массиву и сравнивать его с номером шага алгоритма, можно номера ячеек которые получили свой параметр длины пути в другой массив складывать. (это уже оптимизации)
Yandex
Объявления
10.11.2016, 17:14     Не работает рекурсивная функция
Ответ Создать тему
Опции темы

Текущее время: 01:18. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru