БФС Maze помогите с++

Я пытаюсь сделать лабиринт-решатель, используя поиск по ширине, и отметить кратчайший путь с помощью символа ' * '

На самом деле лабиринт-это просто куча текста. Лабиринт состоит из n x n сетки, состоящей из символов"#", которые являются стенами и периодами."представляя проходимую область / пути. "S" означает начало, " F " - конец. Прямо сейчас эта функция, похоже, не находит решения (она думает, что у нее есть решение, даже когда оно невозможно). Я проверяю ... четыре соседа, и если они 'unfound' (-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;

}
2 2
c++ maze breadth-first-search

2 ответа:

Перебор соседей может быть значительно упрощен(я знаю, что это несколько похоже на то, что предлагает кобра, но это может быть улучшено дальше). Я использую массив ходов, определяющий дельту x и y данного хода следующим образом: 

int moves[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
Обратите внимание, что tis не только перечисляет все возможные ходы из данной ячейки, но и перечисляет их по часовой стрелке, что полезно для некоторых задач. Теперь для обхода массива я использую std::queue<pair<int,int> > Таким образом, текущая позиция определяется парой соответствующих ему координат. Вот как я циклически перебираю соседей клетки gien 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) в моем коде).

Надеюсь, это поможет вам и даст несколько советов, как улучшить ваше кодирование.

0

Несколько комментариев:

  1. Вы можете использовать контейнер очереди в c++, его гораздо проще в использовании
  2. в этой задаче вы можете написать что-то вроде: 
int delta[] = {-1, cols, 1 -cols};

И тогда вы просто можете перебирать все четыре стороны, вы не должны копировать-вставлять один и тот же код.

  1. у вас будут проблемы с границами вашего массива. Потому что вы его не проверяете.
  2. Когда вы основали finish, вы должны прервать цикл
  3. и в последнем цикле вы есть ошибка. Он напечатает * во всех ячейках, в которых вы были (не только оптимальным способом). Он должен выглядеть:
while (finish != start)
{
  maze[finish] = '*';
  finish = prd[finish];
}
maze[start] = '*';

И конечно же этот цикл должен быть в последнем случае, потому что вы не знаете, достигнете ли вы в этот момент конца или нет

PS и его лучше очистить от памяти, которую вы выделили в функцию

0