[解決済み] BFS迷路ヘルプ c++

質問

ブレッドファースト探索を用いた迷路解法を作成し、最短経路を文字'*'でマークしようとしています。

迷路は、実はただのテキストの束です。迷路はn×nのグリッドで構成され、壁を表す"#"と、歩けるエリア/パスを表すピリオド"."で構成されています。S'はスタート、'F'はフィニッシュを表します。 今現在、この関数は解を見つけることができないようです（解がありえないのに解があると思い込んでいます）。 私は4つの隣人をチェックし、それらが「未発見」（-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;

}

解決方法は？

近傍のイテレーションを大幅に簡略化することができます（これはkobraが提案するものと多少似ていますが、さらに改善することができます）。私は、与えられた手の x と y のデルタを定義する moves 配列をこのように使用します。

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

これは、与えられたセルから可能なすべての手をリストアップするだけでなく、いくつかの問題で有用な時計回りの方向にもリストアップすることに注意してください。 さて、この配列をたどるには std::queue<pair<int,int> > このように、現在の位置はそれに対応する座標の組で定義される。以下は、あるセル 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) のビットがあります)。

これが、あなたのコーディングの改善のヒントになれば幸いです。