2

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

迷宫实际上只是一堆文字。迷宫由一个 nxn 网格组成，由作为墙壁的“#”符号和句点“.”组成。代表可步行区域/路径。“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;

}
4

2 回答 2

0

几点评论：

  1. 您可以在 C++ 中使用队列容器，它更易于使用
  2. 在此任务中，您可以编写如下内容：
int delta[] = {-1, cols, 1 -cols};

然后你可以简单地遍历所有四个方面，你不应该复制粘贴相同的代码。

  1. 您将遇到数组边界问题。因为你没有检查它。
  2. 当你建立完成后，你应该打破循环
  3. 在上一个周期中你有一个错误。它将在您所在的所有单元格中打印 * （不仅以最佳方式）。它应该看起来：
while (finish != start)
{
  maze[finish] = '*';
  finish = prd[finish];
}
maze[start] = '*';

当然这个循环应该在最后一个如果，因为你不知道那一刻你是否到达终点

PS最好清除您在函数中分配的内存

于 2012-11-04T19:45:48.483 回答
0

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

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

请注意，它不仅列出了给定单元格的所有可能移动，而且还按顺时针方向列出了它们，这对某些问题很有用。现在要遍历数组，我使用 astd::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)我的代码中的那个位）。

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

于 2012-11-04T20:12:23.377 回答