поиск в ширину — помощь по лабиринту BFS Переполнение стека
Я пытаюсь сделать решатель лабиринта, используя поиск в ширину, и отмечаю кратчайший путь, используя символ ‘*’
Лабиринт на самом деле просто куча текста. Лабиринт состоит из сетки n x n, состоящей из символов «#», которые представляют собой стены и точки «.» представляющие пройденную зону / дорожки. «S» обозначает начало, «F» — конец. В данный момент эта функция, похоже, не находит решения (она думает, что имеет решение, даже если оно невозможно). Я проверяю четырех соседей, и если они «найдены» (-1), они добавляются в очередь для обработки.
Лабиринт работает на нескольких лабиринтах, но не на этом:
...###.#....
##.#...####.
...#.#.#....
#.####.####.
#F..#..#.##.
###.#....#S.
#.#.####.##.
....#.#...#.
.####.#.#.#.
........#...
Чего не хватает в моей логике?
int mazeSolver(char *maze, int rows, int cols)
{
int start = 0;
int finish = 0;
for (int i=0;i<rows*cols;i++) {
if (maze[i] == 'S') { start=i; }
if (maze[i] == 'F') { finish=i; }
}
if (finish==0 || start==0) { return -1; }
char* bfsq;
bfsq = new char[rows*cols]; //initialize queue array
int head = 0;
int tail = 0;
bool solved = false;
char* prd;
prd = new char[rows*cols]; //initialize predecessor array
for (int i=0;i<rows*cols;i++) {
prd[i] = -1;
}
prd[start] = -2; //set the start location
bfsq[tail] = start;
tail++;
int delta[] = {-cols,-1,cols,+1}; // North, West, South, East neighbors
while(tail>head) {
int front = bfsq[head];
head++;
for (int i=0; i<4; i++) {
int neighbor = front+delta[i];
if (neighbor/cols < 0 || neighbor/cols >= rows || neighbor%cols < 0 || neighbor%cols >= cols) {
continue;
}
if (prd[neighbor] == -1 && maze[neighbor]!='#') {
prd[neighbor] = front;
bfsq[tail] = neighbor;
tail++;
if (maze[neighbor] == 'F') { solved = true; }
}
}
}
if (solved == true) {
int previous = finish;
while (previous != start) {
maze[previous] = '*';
previous = prd[previous];
}
maze[finish] = 'F';
return 1;
}
else { return 0; }
delete [] prd;
delete [] bfsq;
}
Решение
Итерации по соседям могут быть значительно упрощены (я знаю, что это несколько похоже на то, что предлагает Кобра, но это может быть улучшено в дальнейшем). Я использую массив ходов, определяющий дельту x и y данного движения следующим образом:
int moves[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
Обратите внимание, что в этом списке не только перечислены все возможные перемещения из данной ячейки, но также перечислены их по часовой стрелке, что полезно для некоторых задач.
Теперь, чтобы пройти массив, я использую std::queue<pair<int,int> > Таким образом, текущая позиция определяется соответствующей ей парой координат. Вот как я циклически перебираю соседние клетки g c:
pair<int,int> c;
for (int l = 0;l < 4/*size of moves*/;++l){
int ti = c.first + moves[l][0];
int tj = c.second + moves[l][1];
if (ti < 0 || ti >= n || tj < 0 || tj >= m) {
// This move goes out of the field
continue;
}
// Do something.
}
Я знаю, что этот код на самом деле не имеет отношения к вашему коду, но, поскольку я учу этому типу проблем, поверьте мне, многие студенты были очень благодарны, когда я показал им этот подход.
Теперь вернемся к вашему вопросу — вам нужно начать с конечной позиции и использовать массив prd, чтобы найти его родителя, затем найти родителя его родителя и так далее, пока вы не достигнете ячейки с отрицательным родителем. Вместо этого вы учитываете все посещенные ячейки, и некоторые из них не находятся на кратчайшем пути от S в F,
Вы можете сломать, как только вы установите solved = true это немного оптимизирует алгоритм.
Я лично думаю, что вы всегда находите решение, потому что у вас нет чеков на падение с поля. ( if (ti < 0 || ti >= n || tj < 0 || tj >= m) немного в моем коде).
Надеюсь, что это поможет вам и даст несколько советов, как улучшить кодирование.
Другие решения
Несколько комментариев:
- Вы можете использовать контейнер очереди в C ++, его гораздо проще в использовании
- В этом задании вы можете написать что-то вроде этого:
int delta[] = {-1, cols, 1 -cols};
И тогда вы просто можете перебирать все четыре стороны, вы не должны копировать и вставлять один и тот же код.
- У вас будут проблемы с границами вашего массива. Потому что вы не проверяете это.
- Когда вы основали финиш, вы должны выйти из цикла
- И в последнем цикле у вас есть ошибка. Он будет печатать * во всех ячейках, в которых вы были (не только оптимальным образом). Это должно выглядеть так:
while (finish != start) { maze[finish] = '*'; finish = prd[finish]; } maze[start] = '*';
И, конечно, этот цикл должен быть последним, если, потому что вы не знаете, в этот момент вы достигли конца или нет
PS А лучше очистить память, которую вы распределили в функции