2012-03-21 11 views
-1

ある単語が2次元のアルファベットの行列に存在するかどうかを調べるのに、それをどのように実装するのかはわかりません。 例えば、我々のような行列がある場合:逆戻りを使って行列内の単語を見つけよう

G O P 
N N A 
A B E 

をし、ルールは1我々は上記の行列は「GONE」の単語が含まれているかどうかを指示する必要があり、その後、任意の位置から垂直及び斜めに、水平方向に移動できるということです。ここでは、最初にすべてのGのposifinを保存し(> 1 Gが存在する場合)、その各位置からチェックを開始できますが、バックトラッキングを使用してチェックする方法はありますか?おかげさまで

+0

はい、バックトラックを使用して解決できます。完全なアルゴリズムを求めていますか? – gbianchi

答えて

0

私はアルゴリズム

はこれが最後の位置であれば、あなたの言葉から始まる手紙は、その位置(次の文字またはleeterの次の位置を渡す)

と機能をバックトラッキング開始 検索コードを擬似しますあなたが探している、あなたはそれを見つける。 N(北)の文字が次の文字であることを確認し、その位置(現在の位置)と次の文字(または次の文字の文字列内の位置)で関数を再度呼び出します。 NEなどのチェックレターでない場合。 完了して一致するものが見つからない場合は、前の呼び出しに戻ります。

HTHについては、必要に応じて説明を求めてください。

2

このゲームはBoggleと呼ばれています。ここにはa nice thread on SO(コード例を含む)があります。

関連する問題