問題タブ [boggle]

単語を取得してボード上に存在するかどうかを確認する機能を含むコーディング ブートキャンプ用の BoggleBoard ゲームを実行しています。単語が存在するかどうかを確認する私の方法は、私が「隣接行列」と呼んだものを作成することでした（これは実際の隣接行列ではないことを理解しています。これは、文字の実際の位置を連鎖させるのではなく、私が思いついたものです探していました）。3x3 グリッドのアイデアは次のとおりです。

0 | 1 | 2
3 | 4 | 5
6 | 7 | 8

対応する「隣接行列」は次のとおりです。

アイデアは、実際にボード上の単語を見つける必要があるのではなく、単語の文字の長さに対応する別の配列を作成することです。単語の各文字には、その単語がボード上に表示されるすべての場所のインデックスを示す配列内の配列があります。次に、基本的に、隣接行列ごとに現在の文字に隣接するセルが、次の文字の位置とインデックスを共有しているかどうかを確認します。

例: ボード:
C | A
C | T

探しているもの: 猫

最初の文字 C のインデックス = 0
- インデックス 0 に隣接するセル = [1,2,3] と [0,1,3] を連結 => [0,1,2,3]
- 文字 A はいずれかの 0 ,1,2,3? はい
-
次の文字 A のインデックスを続行 = 1
- インデックス 1 に隣接するセル = 0,2,3
- 文字 T は 0,2,3 のいずれかに出現しますか? はい
単語が見つかりました

私は現在、ゲームプレイの 4x4 グリッド用にゲームをセットアップしており、隣接マトリックスにハードコーディングしています。ユーザー入力に基づいてゲームのサイズをボードにし、ボードのサイズに応じて隣接行列を動的に作成する方法があるかどうかを確認したいと思います。これは可能ですか？

(これは実際の隣接行列ではないことを理解しています。これは、探していた文字の実際の位置をチェーンするのではなく、私が思いついたものです。)

私は Coursera のアルゴリズム、パート IIコースに登録しました。課題の 1 つは、ボーグル ゲームを解くことです: http://coursera.cs.princeton.edu/algs4/assignments/boggle.html

名誉規定では、解決策を公に投稿しないことが求められているため、代わりに基本アルゴリズムの疑似コードを次に示します。

ディクショナリは Trie を使用して実装されます。

上記のコードは機能し、私は割り当てに合格しましたが、動的プログラミングを使用したより高速なソリューションを主張する次のブログ投稿に出くわしました。

気の利いた動的計画法を使用して、単語 (この場合は辞書から) をボードから構築できるかどうかをすばやく確認できます。

動的計画法の考え方の要点は次のとおりです。

ボードの [i, j] 番目の位置 (終了位置) で長さ k の単語が見つかるには、その単語の k-1 番目の文字が [i, j] の隣接するセルの 1 つに配置されている必要があります。 j].

基本ケースは k = 1 です。

長さ 1 の文字は、ボードの [i, j] 番目のセルで見つかります (終了位置)。単語内の唯一の文字は、ボードの [i, j] 番目の位置の文字と一致します。

動的計画法テーブルに基本ケースが入力されると、その上に長さ k (k > 1) の任意の単語を構築できます。

残念ながら、著者の説明は不十分であり、私は彼の解決策をたどることができません。私はしたいのですが、ここの誰かが私にそれを説明してくれることを願っています.

PS:

1. DPを使用していないため、この質問の複製ではありません。それらの重複した幸せな指を抑えてください。

2. 私の側では十分な努力が示されており、誰にも宿題をするように頼むことはありません. 私はすでに独自の解決策を持っています。私が興味を持っているのは、問題を解決するためのより良い方法があればそれを学ぶことです。

ありがとう！

合計16文字の4x4ボードがあります。この配列の [2,1] は、3 行目の 2 列目の文字を表します。

[2,1] のようなペアを、16 個の文字列 (文字) の配列で表されるゲーム ボード上の単一の文字にリンクする方法を見つけようとしています。

最終的な目標は、提供されたゲーム ボードと座標に基づいて、関数が単語の文字列を生成することです。

コメント付きの JSFiddle: https://jsfiddle.net/8euxzgy2/4/

.txt ファイルから読み取る、または既にハード コードされているボグル プログラムの例をたくさん見てきましたが、単語リストの URL 接続を使用して、それをボグル ゲームのグリッドと比較できますか?