Codility から次のタスクにアプローチする方法についてヒントを教えてください: https://codility.com/programmers/task/hilbert_maze/
迷路を生成し、BFS を使用して最短経路を検索することで、最短経路を見つけることができますが、最悪の場合の時間の複雑さは O(N) であると予想されるため、これは正しい方法ではないと思います行く。BFS の時間計算量は O(|V| + |E]) で、V は頂点の数、E はエッジの数です。たとえば、N = 3 の場合、サイズが 17x17 のグリッドがあり、3 ステップだけではパスを見つけることができないことは直感的に明らかです。
したがって、示された時間計算量が間違っていて、M^2 のようなものである必要があるか、グラフ アルゴリズムを使用せずに 2 点間の距離を単純に計算するための簡単なトリックがあります。与えられた 2 点のヒルベルト距離を計算するためのアルゴリズムをいくつか見つけました (ここで必要な場合)。これはビット操作などを使用しますが、まったく理解できませんでした。また、このタスクの目標は、既存の式を使用せずに距離を計算する方法を自分で見つけることだと思います。
このタスクを解決し、さらに私を助けてくれる人はいますか? ありがとう！