問題タブ [hamiltonian-path]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
c++ - バックトラッキングを使用して正方形グリッドへのパスを見つけるこのコードは正しいですか?
私は、antti lakesonen の競技用プログラミング ハンドブックを読んでいて、いくつかの最適化が適用されたグリッド パスを見つけるためのバックトラッキングに出くわしました。一言で言えば、グリッドを横切る有効なパスのルールは次のとおりです。
dimension = 7これで、所要時間~400msと合計の正方形グリッドで正常に機能するこのコードを作成しましたpaths : 111712。ここに 2 つのクエリがあります。
-->dimension = 9検索の最初の有効なパスでさえ、報告するのに多くの時間がかかります。私は無限ループに陥っていますか？
even number of dimension--> 2,4,6 などのグリッド パス検索が提供されてanswer 0います。2*2 および 4*4 グリッドのパスを手動で見つけようとしましたが、そのようなパスを見つけることは不可能であることがわかりましたが、正方形のグリッドの寸法でさえ上記のようなパスを持つことができないことを形式的または論理的に証明する方法がわかりません。
これが私のコードです:
コメントARRAY_BASED_CONSTANT_GRIDして、グリッド ディメンションのユーザー入力を有効にします。
誰かがこれで私を助けることができますか? 前もって感謝します ：）
PS: 私のコーディング慣行により、コードをわかりやすくするためにコード全体を貼り付ける必要がありました。stackoverflow では最小限の必要なコードのみを貼り付ける必要があることはわかっていますが、ここでは、コードを分析するために本当に必要なものがわかりません!