6

私のプログラムは、ファイルからの入力として char 配列を取ります。配列は次のようになります。

"#########",
"# #     #",
"# ##  # #",
"#     # #",
"### # ###",
"#   # # #",
"# # #####",
"#   #   #",
"#########",

[1,1] から [width - 1,height - 1] で終わるこの迷路を解くために、DFS と BFS を実装しています。

迷路を表すツリーを作成し、各アルゴリズムを使用してツリーをトラバースすることを考えました。

各行から開始し、空のセルをスキャンします。各空のセルで、その右、左、および下にあるすべてのセルがそのセルの子になります。次のようになります。

    for (int i = 0; i < width; i++)
    {
        for (int j = 0; j < height; j++)
        {
            if (isEmpty(maze[i][j]))
                    {
                         putChildren(maze[i-1][j], maze[i][j+1], maze[i+1][j]);
                         //this will check if it's a wall first
                    }       
    }

このようにツリーを実装し、それを使用して DFS と BFS でツリーをトラバースすることは実行可能な戦術ですか、それとも別の方法で行う必要がありますか?

4

2 に答える 2

3

素敵なプロジェクト、私はそのようなものが大好きです。ところで、方向性試行アルゴリズム (いわゆる A* アルゴリズム) を検討しましたか?特に 2D 配列で作業している場合は、その方が良いと思います。通常の場合、他の方法よりもパフォーマンスが高く、リンクされたセルを使用する必要はありません。このアルゴリズムには、「最初に方向を試す」方法にリンクされたメモリを含む、ある種の改善もあります。もちろん、あなたの方法に問題はありませんが、処理する行列が本当に巨大な場合を考慮してください。

于 2013-11-06T20:22:00.813 に答える