3

再帰によって迷路を解くことができるプログラムを作成しようとしています。具体的には、オンラインで見つけることができるいくつかの手順に基づいてコードを作成しています。

  1. if (x,y out of maze) return false
  2. (x,y が目標) の場合、true を返す
  3. (x,y が開いていない) の場合、false を返す
  4. x、y をソリューション パスの一部としてマークする
  5. if (FIND-PATH(x,y の北) == true) true を返す
  6. if (FIND-PATH(x,y の東) == true) true を返す
  7. if (FIND-PATH(x,y の南) == true) true を返す
  8. if (FIND-PATH(x,y の西) == true) true を返す
  9. ソリューション パスの一部として x,y のマークを外す
  10. false を返す

このアルゴリズムに関する他の質問を少なくとも 2 つ見たことがありますが、問題がまったく同じではないことは確かです。

bool path (string maze[], int x, int y){
    values val;
    bool check;
    //for (int k=0; k<val.xDim; k++) cout<<maze[k]<<endl;
    cout<<x<<":"<<y<<endl;
    if (x>val.xDim || y>val.yDim || x<0 || y<0) {cout<<"end\n"; return false;  }
    if (maze[x][y]=='x') return true;                           //If exit is reached
    if (maze[x][y]=='%' || maze[x][y]=='+') return false;       //If space is filled
    maze[x][y]='+';
    if (path(maze, x-1, y)==true) return true;
    cout<<"endtwo\n";
    if (check=path(maze, x, y+1)==true) return true;
    if (path(maze, x+1, y)==true) return true;
    if (path(maze, x, y-1)==true) return true;
    maze[x][y]='.';
    return false;
}

int main(){
    if (path(maze, val.startX-1, val.startY)==true) {
        for (int k=0; k<val.xDim; k++) cout<<maze[k]<<endl;
    } else cout<<"No solution found.\n";
}

サンプルの迷路は次のとおりです (e は入り口、x は出口です)。

%e%%%%%%%%%
%...%.%...%
%.%.%.%.%%%
%.%.......%
%.%%%%.%%.%
%.%.....%.%
%%%%%%%%%x%

出力：

-1:1
end
No solution found.

私が知る限り、path メソッドは、迷路の外にある (false を返す) 入り口の真上にあるスペースをチェックすることから始めるべきです。これに続いて、東 (など) をチェックする必要があります。ただし、実行すると、関数は false を返し、次の if ステートメントに進むことができません。これは、"end" が出力されているのに対し、"endtwo" (ノース チェックの後に見つかった) が出力されていないという事実によって示されます。再帰ロジックまたは再帰の実装に何らかの問題があるかどうかはわかりません。そのため、これについて明確にしたいと考えています。

前もって感謝します！

4

2 に答える 2

4

最初のチェックインでbool path(...)は、x==-1 であるため x<0 が検出されるため、関数は返さfalseれて終了し、メイン プログラムはfalseへの呼び出しから結果を取得し、必要pathなものを出力して終了します。

有効な位置でチェックを開始する必要があります。

于 2013-04-19T18:52:41.267 に答える