Рекурсивно избежать Лабиринта - PullRequest
Новая
       3

Рекурсивно избежать Лабиринта

0 голосов
/ 10 декабря 2011

Домашнее задание, я просто спрашиваю, правильна ли моя логика, и если нет, то в каких случаях я пропускаю, а не как это сделать.

У меня есть задание, в котором мы должны были создать случайно сгенерированный лабиринт из файла данных, предоставленного нам.Каждой комнате присваивается номер от 1 до 100, и она имеет (до) 4 смежных комнат: север, восток, юг и запад.Комната без смежной комнаты будет иметь соседнюю комнату с отрицательным идентификатором.Наш «человек» случайно попадает в одну из этих комнат, и мы должны найти выход.Снаружи обозначен номер комнаты 0.

У меня есть все, кроме рекурсии, которая почти завершена.Это мое решение: 

void Graph::findPath( Room * curRoom )
{
    if( curRoom -> myNumber == 0 )
    //Escaped!
    else
    {
       if( curRoom -> North -> visited == false )
    {   
        curRoom -> visited == true;
        findPath( curRoom -> North )
    }

    if( curRoom -> East -> visited == false )
    {   
        curRoom -> visited == true;
        findPath( curRoom -> East )
    }
    if( curRoom -> South -> visited == false )
    {   
        curRoom -> visited == true;
        findPath( curRoom -> South )
    }
    if( curRoom -> West -> visited == false )
    {   
        curRoom -> visited == true;
        findPath( curRoom -> West )
    }
    }

}

Я думаю, что оно правильно.Меня беспокоит только то, что нам нужно распечатать правильный путь, который, как я знаю, можно сделать, но я не знаю, как это сделать, не печатая и неправильные.

Спасибо за ваше время.

Если какая-либо информация отсутствует, дайте мне знать, и я отвечу в спешке.

1 Ответ

1 голос
/ 10 декабря 2011

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

Возможно, вам следует добавить комнату в список (стек) «мест на пути» перед повторением, удаляя его перед возвратом, если из этой комнаты нет выхода.Когда вы выходите, в этом списке указывается путь, который вы выбрали.

...