c++ - BFS 迷宫帮助 C++

Question

我正在尝试使用广度优先搜索制作迷宫求解器，并使用字符“*”标记最短路径

迷宫其实就是一堆文字。迷宫由 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;

}

Answer 1

遍历邻居可以大大简化(我知道这有点类似于 kobra 的建议，但可以进一步改进)。我使用移动数组定义给定移动的 x 和 y 增量，如下所示:

int moves[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};

请注意，它不仅列出了给定单元格的所有可能移动，而且还按顺时针方向列出了它们，这对某些问题很有用。现在遍历数组我使用 std::queue<pair<int,int> >这样当前位置就由对应的一对坐标定义。以下是我如何循环遍历 gien cell 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后即可中断这将稍微优化算法。

我个人认为您总能找到解决方案，因为您没有检查是否会掉下 field 。 (我代码中的 if (ti < 0 || ti >= n || tj < 0 || tj >= m) 位)。

希望这对您有所帮助，并为您提供一些改进编码的技巧。