2

単語がランダムな文字 (AZ) の 4x4 グリッドに存在する場合、どのように検索しますか?誰かがこの問題に取り組む効果的な方法の正しい方向に私を導くことができますか.

条件は次のとおりです。

  • 単語は隣接する文字から形成されます
  • 単語は、水平、垂直、または斜め左、右、または上下に形成できます
  • 1 つの単語内で文字セルを複数回使用することはできません。

助けてくれてありがとう！

4

3 に答える 3

2

これをグラフの問題として扱うことができます。グリッドをグラフに変換します。各頂点はグリッド内のセルを表し、頂点間のエッジはこれらのセル間の有効な動きを表します。

そこから、次の再帰的アルゴリズムを使用して、単語SがグラフGで見つかるかどうかを判断できます。

FindWord（G、S）：
1.CをSの最初の文字に設定します。
2.最初の文字を削除してS'をSに設定します。
3. Gのすべての頂点Vについて：
  3.1。Vの文字がCでない場合は、次の頂点に進みます。
  3.2。CheckPaths（G、S'、V、{}）がtrueを返す場合は、trueを返します。
4.falseを返します。

CheckPaths（G、S、V、Visited）：
1. Sが空の場合、trueを返します。
2.CをSの最初の文字に設定します。
3.最初の文字を削除してS'をSに設定します。
4.「訪問済み」を「訪問済み」∪{V}に設定します。
5.Vに接続されているすべてのセルV'の場合：
  5.1。V'∈Visitedの場合、次の頂点に進みます。
  5.2。V'の文字がCでない場合は、次の頂点に進みます。
  5.3。CheckPaths（G、S'、V'、Visited'）がtrueを返す場合は、trueを返します。
6.falseを返します。

実際の実装は少し異なる可能性があります（たとえば、Visitedのコピーを作成せず、パスが失敗したと判断した後に頂点を削除して単一のセットを共有することをお勧めします）が、これが基本的な考え方です。それをするために。

于 2012-01-27T23:46:53.450 に答える
1

4X4 グリッドで作業している場合は、非常に単純なはずです。単語の最初の文字をスキャンし、その単語がグリッドから完成できるかどうかをあらゆる方向に検索します。

グリッドが非常に大きい場合、および/または多数の検索を実行している場合は、最初にグリッドを前処理することをお勧めします。例えば。数文字ごとに (一般に k 文字を追跡したいので、k-gram と呼びましょう)、それらが配置されている場所のリストを保持できます。検索するときは、まずその単語の k-gram の場所を探します。

于 2012-01-27T23:28:34.107 に答える
1

文字と空白の両方を持つグリッドの表現から始めます。

そのようなグリッドと開始文字をパラメーターとして取り、可能な単語のリストを返すルーチンを作成します。

このようなグリッドに対して、特定の文字に隣接する各文字を返す反復子を作成します。空白を認識し、返されません。

そして、文字とグリッドを取得し、文字をグリッドから削除し、隣接する文字ごとに、新しいグリッドと新しい文字でそれ自体を呼び出すルーチンを作成します。

本当に 1 つの単語を検索したい場合は、これらのルーチンに渡すことができるので、一致しない場合はすぐに失敗する可能性があります。

それ以外の場合は、これを使用して単語の完全なリストを生成できます。

于 2012-01-27T23:43:30.967 に答える