如何计算 BFS 算法中的移动？ （迷宫中的最短路径）

Question

所以我尝试实现一个 BFS 算法并真正理解它是如何工作的（创建某种 "my version"，从头开始，只看图表和一些伪代码），这就是我最终得到的：

#include<iostream>
#include<string>
#include<fstream>
#include<queue>

using namespace std;



    void main(int argc, char *argv[])
    {
        // Deklaracja uchwytu do pliku (tylko do odczytu pliku)
        ifstream plik(argv[1]);
        // Tablica stringow - przechowujaca wartosci pol 12x12
        string labirynt[12];
        pair <int, int> start;
        pair <int, int> koniec;
        // Wektor par - działa jak tablica, przechowuje pary współrzędnych pól
        queue <pair<int, int>> kolejka;
        // Tablica odwiedzin - sprawdza czy pole zostalo odwiedzone, 0 jesli nie, 1 jesli tak
        bool odwiedzone[12][12] = { 0 };
        // Zmienna pomocnicza - bo getline sluzy do umieszczania danych w stringu, nie w tablicy znakow
        int i = 0;
        // Pętla wczytująca tekst z pliku do tablicy labirynt
        while (getline(plik, labirynt[i]))
        {
            i++;
        }

        // Wyszukanie początku i końca w labiryncie (A i B)
        for (int i = 0; i < 12; i++)
        {
            for (int j = 0; j < 12; j++)
            {
                if (labirynt[i][j] == 'A')
                {
                    start.first = i;
                    start.second = j;
                }
                if (labirynt[i][j] == 'B')
                {
                    koniec.first = i;
                    koniec.second = j;
                }
            }

        }


        // Ustawiamy pole startowe jako odwiedzone - żadne pole nie może być odwiedzone więcej niż 1 raz
        odwiedzone[start.first][start.second] = true;



        // Wiersz i kolumna bieżącego wierzchołka
        int w, k;




        kolejka.push(start);

        // Dopóki kolejka nie jest pusta
        while (!kolejka.empty())
        {
            // Pobieramy z kolejki wiersz i kolumnę bieżącego wierzchołka
            w = kolejka.front().first;
            k = kolejka.front().second;
            // Usuwamy parę z kolejki
            kolejka.pop();


            // Sprawdzamy czy dotarliśmy do wyjścia
            if (w == koniec.first && k == koniec.second)
                break;

            // Przeglądamy sąsiadów bieżącego wierzchołka

            for (i = -1; i <= 1; i++)
            for (int j = -1; j <= 1; j++)
            {

                if ((i != j) && (!i || !j))
                if (labirynt[w + i][k + j] == ' ' && !odwiedzone[w + i][k + j])
                {
                    odwiedzone[w + i][k + j] = true;
                    pair <int, int> para;
                    para.first = w + i;
                    para.second = k + j;
                    kolejka.push(para);
                    cout << kolejka.front().first << endl;
                    cout << kolejka.front().second << endl;
                }
            }



        }
    system("PAUSE");
    }

这是我使用的示例迷宫（程序从放在 .exe 上的文件中读取）

xxxxxxxxxxxx
xxA  xxxxxxx
xx x  xxxxxx
x  x  xxxxxx
xx x    xxxx
xx xxx xxxxx
x   xxxxxxxx
x x  xxxxxxx
x xxx xxxxxx
x    xxxxxxx
xxx     Bxxx
xxxxxxxxxxxx

它有效（显示它经过并找到 B 的迷宫中每个字段的坐标），但我不知道如何计算通过最短路径所需的移动。

Answer 1

而不是使用 odwiedzone[w + i][k + j] = true; 来检查之前已经走过的坐标，使用类似 odwiedzone[w + i][k + j] = now + 1 的东西来计算从开始到那个位置的步数：

// first, declare all odwiedzone[][]=-1
...

odwiedzone[start.first][start.second] = 0;
// first position needs 0 step
...
            for (i = -1; i <= 1; i++)
            for (int j = -1; j <= 1; j++)
            {

                if ((i != j) && (!i || !j))
                if (labirynt[w + i][k + j] == ' ' && odwiedzone[w + i][k + j]==-1)
                {
                    odwiedzone[w + i][k + j] = odwiedzone[w][k]+1;
                    //next position = now position + 1

                    pair <int, int> para;
                    para.first = w + i;
                    para.second = k + j;
                    kolejka.push(para);
                    cout << kolejka.front().first << endl;
                    cout << kolejka.front().second << endl;
                }
            }

Answer 2

我看到有 2 种方法可以达到您的要求：

1. 使用单独的队列来存储与每个单元格相关的距离，例如start 将有 0，start 的每个邻居将有 1，依此类推。每次添加新邻居时，他的值将是到当前单元格的距离 + 1。第二个队列中的目的地值将为您提供路径长度。

2. 在队列中添加邻居时，记录他的parent。因此，当您找到源头时，您可以重建路径并计算步数。