2次元配列の文字の検索について

Question

お世話になります。今Boggleゲームというもののプログラムを考えているのですが、配列の検索についてお聞きしたいことがあります。
Boggleゲームは、4×4の正方形のマス1つ1つにアルファベットが書いてあるサイコロが入っており、
縦横斜めから英単語がいくつ出来るかを探して競うゲームです。今回は英単語に限らず、指定した文字列がこのルールで見つけられるかを試します。
もしその文字列がこのルールで見つかればtrue、見つからなければfalseを返します。
例えば、
A B C D
E F G H
 I J K L
M N O P
という2次元配列があり、この中からABGLPを探すとすると、AとBは隣り合っており、BとGは斜めで隣り合っており、GとLも斜めで隣、 LとPは上下で隣なので、ABGLPはOKです。
しかし例えばACBを検索すると、CとBは隣り合っていてもAとCは隣り合ってないので、この時点でアウトです。
ちなみに同じ配列のインデックスの文字は2度使えません。例えば、ABCGBを検索すると、隣り合った文字同士なのでOKですが、同じインデックスにあるBを2度使っているのでアウトです。
以上のルールで、文字1つ1つを検索するプログラムを考えているのですが、どのようにすればいいのかがわかりません。
例えばAFCBを検索するとなると、まずAのまわりにFがあるかどうかを検索するので（Aは角なので）、[0][1],[1][0],[1][1]の３つを探せばいいだけですが（この場合は[1][1]=F）、
次にFの周りにCがあるかを検索すると計8つのインデックスの中身を調べなければなりません（この場合は[0][2]=C）。
そして最後にCの周りにBがあるかどうかで計5つのインデックスの中身を調べます（この場合[0][1]=B）。
常にFの検索のように3×3の検索ならfor文2つで簡単に出来ますが、検索する文字によっては角の検索になったり端の列の検索になったりと検索範囲が変わってしまいます。
しかも同じインデックスの中身は2度使えないのでもしそのインデックスにヒットしたら飛ばさなければなりません。
これをどのように検索すればいいのかがわかりません。全ての可能なケースのfor文を用意するとすごい長さになってしまいます。
どなたか宜しくお願いします。

Yanch · Accepted Answer

> しかし最後に一つだけみおとしがあり、もし2次元配列に同じ文字が2つ以上あった場合の検索です。
> この場合何通りかの検索をしなければならないので、コードを変えなくてはいけません・・・
> 例えば
> REDM
> BANO
> TQDF
> LOEV
> から、DOTを探すと、Dが2つあるので、最初の頭を探すループの時に、2つのDを記録して、2次元配列の検索を2回やらなければなりません。
> どのように工夫したらよいでしょうか。以下がコードです。アルゴリズムは変わってません。
その場合のアルゴリズムも考えてみましたが、結構複雑になるので、
残念ですが、説明しにくいです。

いくつか解法はあると思いますが、

●開始位置の候補場所を列挙する。
●全ての開始位置から、経路探索などの方法で、問題に一致する経路情報を作成する。
●経路上から、重複する経路を削除する。
●残った経路があれば、true、なければfalse

と言った方法が有利じゃないかなと、想像してます。

経路情報を構造的に管理するなど必要ですが、これで解決出来ると思われます。
詳細の説明はご勘弁ください。

Yanch · Answer

●
>> if ((j < 0) || (j >= row) || (0 > k) || (k >= col)) {
> j == rowと、k == colの場合は、gameboardの範囲外ですよ。
元のままで問題なかったみたいです、ごめんなさい。

●
> あるいは文字がヒットした場合、2次元配列のループを最初に戻し、新しい検索対象のためのループにするために、一気にループを２つbreakする方法がわかりませんでした
これは、
continute LOOP;
とすれば、良いと思います。

●
もう一息という感じでありますね。

Yanch · Answer

●

> if ((j < 0) || (j >= row) || (0 > k) || (k >= col)) {
j == rowと、k == colの場合は、gameboardの範囲外ですよ。

●
少しコメントを入れるようにしましょう。

あと、メソッド化できそうな部分は、メソッド化です。

●
> 　　　　for (int i = 0; i < row; i++) {
> 　　　　　　for (int j = 0; j < col; j++) {
> 　　　　　　　　work[i][j] = ' ';
> 　　　　　　}
> 　　　　}
work の初期化を最後の方でやっているつもりみたいですが、
かならず通とは限らないように見えます。

●コメントの例
　　　　/*
　　　　 * 最初の１文字目の位置を探す
　　　　 */
　　　　for (int i = 0; i < row; i++) {
　　　　　　for (int j = 0; j < col; j++) {
　　　　　　　　if (gameboard[i][j] == charValueArgs[0]) {
　　　　　　　　　　nowRow = i;
　　　　　　　　　　nowCol = j;
　　　　　　　　　　break;
　　　　　　　　} else {
　　　　　　　　　　blt = false;
　　　　　　　　}
　　　　　　}
　　　　}
など

●
ちゃんと見てないですが、bltを用いて、判定しているみたいですが、
bltのtrue、falseの切り替えがわかりにくい様に見えます。
この部分をtraceしなおす等すると、バグを見つけやすくなると思います。

Tacosan · Answer

当該インデックスの文字を使ったかどうかを覚えておくフラグでも作るかな.
あと, 「検索する文字列に決して現れない文字」があるなら, 与えられた文字配列を拡張して「そのような文字」を周囲に配置しておくと「はみ出したかどうか」の判定はしなくて済みます.
実行時の速度を気にしなくていいなら, 「このような設定を行うドライバメソッド」と「実際に探索を行う再帰的探索メソッド」に分割したほうが楽かもしれない.

Yanch · Answer

> if (周りにi文字目の文字があるか？(r, c)) {　←この部分でどう検索したらいいのかがわかりません。

> 質問欄にも書きましたように、角の検索、端の行列の検索、中の検索で検索範囲が変わり検索方法を変えないといけないように思えます。
> ABCGBを検索する場合、Gはその周りの8つの検索になるのでfor文2つを普通に回せば出来ますが、Aの周りのBを検索する時にGと同じやり方をすると配列の範囲外を検索することになってしまいエラーがでます。
> 同様にBの周りを検索すると、その周りの5つの検索だけでよく、Bより上のインデックスは配列の外になってしまいます。
> if (周りにi文字目の文字があるか？(r, c)) {　←このif文の中身は、上であげた角、行列、中、全ての場合の検索をif文で分けてかかないといけないのでしょうか。
そこのところも工夫してあげれば、
for (int j = (r - 1); j <= (r + 1); j++) {
　　for (int k = (c - 1); k <= (c + 1); k++) {
　　　　if (jが範囲外 || kが範囲外) {
　　　　　　continue;
　　　　}
　　　　文字をチェック(j, k);
　　}
}

のような感じにすれば、それほど複雑にはならないと思われますよ。

osamuy · Answer

ちょっくらrubyで書いてみた：

KW = 'AFCB';
DIR2 = [[1,0],[1,1],[0,1],[-1,1],[-1,0],[-1,-1],[0,-1],[1,-1]];
$Map = DATA.readlines.collect{|s|s.chop.split( // ); }
$VRAM = $Map.collect{|e|Array.new( e.length ); }
$Dir1 = []; ( 1 ... $Map.length-1 ).each{|i|( 1 ... $Map[0].length-1 ).each{|j| $Dir1 << [i,j]; } };
def explore( kw, idx, dir, tracker, &block )
  yield( tracker ) if kw.length == idx;
  c = kw[ idx ]; x0, y0 = tracker[ -1 ];
  dir.each do |vec|
    x = x0 + vec[0]; y = y0 + vec[1];
    if $Map[ x ][ y ] == c && $VRAM[ x ][ y ] != 1 then
      tracker << [ x, y ]; $VRAM[ x ][ y ] = 1;
      explore( kw, idx + 1, DIR2, tracker, &block );
      $VRAM[ x ][ y ] = nil; tracker.pop;
    end
  end
end
explore( KW, 0, $Dir1, [[0,0]] ) do |tracker|
  tracker.shift;
  tracker.each{|pos| p [ pos[0], pos[1], $Map[ pos[0] ][ pos[1] ] ]; }
end
__END__
      
 ABCD 
 EFGH 
 IJKL 
 MNOP 
      
実行結果はこんな感じ：
C:\>ruby a.rb
[1, 1, "A"]
[2, 2, "F"]
[1, 3, "C"]
[1, 2, "B"]

ってやってる事は、No.1さんの回答と似たようなもんだったり。

Yanch · Answer

こんな感じでイメージは掴めるじゃない？

public class Sample {
　　
　　private String[][] map = {
　　　　　　{"A", "B", "C", "D"}, 
　　　　　　{"E", "F", "G", "H"}, 
　　　　　　{"I", "J", "K", "L"}, 
　　　　　　{"M", "N", "O", "P"}};
　　
　　private String[][] work = null;
　　
　　public static void main(String[] args) {
　　　　Sample app = new Sample();
　　　　System.out.println(app.test("ABCGB"));
　　}
　　
　　public boolean test(String testString) {
　　　　最初の１文字目の位置を探す。
　　　　r = 最初の１文字目の行
　　　　c = 最初の１文字目の列
　　　　if (最初の１文字目が見つからない) {
　　　　　　return false;
　　　　}
　　　　ワーク配列をクリア(work);
　　　　使用済み文字にマーク(r, c);
　　　　
　　　　for (int i = 1; i < testString.length(); i++) {
　　　　　　if (周りにi文字目の文字があるか？(r, c)) {
　　　　　　　　if (その文字の位置は使用済みであるか？) {
　　　　　　　　　　return false;
　　　　　　　　}
　　　　　　　　r = i文字目の行
　　　　　　　　c = i文字目の列
　　　　　　　　使用済み文字にマーク(r, c);
　　　　　　}
　　　　}
　　　　return true;
　　}
}

> 全ての可能なケースのfor文を用意するとすごい長さになってしまいます。
そのような印象は受けませんよ。

2次元配列の文字の検索について

> しかし最後に一つだけみおとしがあり、もし2次元配列に同じ文字が2つ以上あった場合の検索です。

●

この回答への補足

●

この回答への補足

当該インデックスの文字を使ったかどうかを覚えておくフラグでも作るかな.

この回答への補足

> if (周りにi文字目の文字があるか？(r, c)) { ←この部分でどう検索したらいいのかがわかりません。

この回答への補足

ちょっくらrubyで書いてみた：

この回答への補足

こんな感じでイメージは掴めるじゃない？

この回答への補足

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

> if (周りにi文字目の文字があるか？(r, c)) {　←この部分でどう検索したらいいのかがわかりません。