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

質問

お世話になります。今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文を用意するとすごい長さになってしまいます。
どなたか宜しくお願いします。

回答No.7

Yanch · ベストアンサー

> しかし最後に一つだけみおとしがあり、もし2次元配列に同じ文字が2つ以上あった場合の検索です。
> この場合何通りかの検索をしなければならないので、コードを変えなくてはいけません・・・
> 例えば
> REDM
> BANO
> TQDF
> LOEV
> から、DOTを探すと、Dが2つあるので、最初の頭を探すループの時に、2つのDを記録して、2次元配列の検索を2回やらなければなりません。
> どのように工夫したらよいでしょうか。以下がコードです。アルゴリズムは変わってません。
その場合のアルゴリズムも考えてみましたが、結構複雑になるので、
残念ですが、説明しにくいです。

いくつか解法はあると思いますが、

●開始位置の候補場所を列挙する。
●全ての開始位置から、経路探索などの方法で、問題に一致する経路情報を作成する。
●経路上から、重複する経路を削除する。
●残った経路があれば、true、なければfalse

と言った方法が有利じゃないかなと、想像してます。

経路情報を構造的に管理するなど必要ですが、これで解決出来ると思われます。
詳細の説明はご勘弁ください。

お礼

ありがとうございます。
色々やってみたのですが、全てのケースで成功させることがなかなかできませんでした。
今回は同じ文字は２つまでしかないという幸いな条件があったのですが、やはり検索する文字によってエラーがでました・・・
むずかしいですね・・・。

回答No.6

Yanch

●
>> if ((j < 0) || (j >= row) || (0 > k) || (k >= col)) {
> j == rowと、k == colの場合は、gameboardの範囲外ですよ。
元のままで問題なかったみたいです、ごめんなさい。

●
> あるいは文字がヒットした場合、2次元配列のループを最初に戻し、新しい検索対象のためのループにするために、一気にループを２つbreakする方法がわかりませんでした
これは、
continute LOOP;
とすれば、良いと思います。

●
もう一息という感じでありますね。

補足

ありがとうございます。ループをぬける方法は、ラベルではなくわざとi、j、kの値を範囲外に設定してbreakさせました。
よって正常に動かすことができました。

しかし最後に一つだけみおとしがあり、もし2次元配列に同じ文字が2つ以上あった場合の検索です。
この場合何通りかの検索をしなければならないので、コードを変えなくてはいけません・・・
例えば
REDM
BANO
TQDF
LOEV
から、DOTを探すと、Dが2つあるので、最初の頭を探すループの時に、2つのDを記録して、2次元配列の検索を2回やらなければなりません。
どのように工夫したらよいでしょうか。以下がコードです。アルゴリズムは変わってません。

public class DiceTray {

private char[][] gameboard;
private int row, col;
private char[][] work;

public DiceTray(char[][] array) {
row = array.length;
col = array[0].length;
gameboard = array;
work = new char[row][col];
}

public boolean stringFound(String search) {

boolean blt = false;
int nowRow = 0, nowCol = 0;
int charValueArgsLength = search.length();
char[] charValueArgs = new char[charValueArgsLength];

int searchLength = charValueArgsLength - 1;
search.getChars(0, charValueArgsLength, charValueArgs, 0);

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;
}
}
}

work[nowRow][nowCol] = charValueArgs[0];

for (int i = 1; i <= searchLength; i++) {
for (int j = (nowRow - 1); j <= (nowRow + 1); j++) {
for (int k = (nowCol - 1); k <= (nowCol + 1); k++) {
if ((j < 0) || (j > row - 1) || (0 > k) || (k > col - 1)) {
continue;
} else if (charValueArgs[i] == gameboard[j][k]) {
if (work[j][k] == gameboard[j][k]) {
blt = false;
i = searchLength + 1;
j = nowRow + 2;
k = nowCol + 2;
} else {
blt = true;
nowRow = j;
nowCol = k;
work[j][k] = charValueArgs[i];
j = nowRow + 2;
k = nowCol + 2;
}
} else {
if (j == nowRow + 1 && k == nowCol + 1) {
i = searchLength + 1;
j = nowRow + 2;
k = nowCol + 2;
} else {
blt = false;
}
}
}
}
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
work[i][j] = ' ';
}
}
return blt;
}

}

回答No.5

Yanch

●
> 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しなおす等すると、バグを見つけやすくなると思います。

補足

お世話になります。バグを一つみつけたのですが、どうなおしたらいいかがわかりません
以下は2次元配列の中から検索対象の文字を探すループです

LOOP: for (int i = 1; i <= searchLength; i++) {　//検索する文字のインデックス分繰り返す。

for (int j = (nowRow - 1); j <= (nowRow + 1); j++) {　//2次元配列のループ（列）

for (int k = (nowCol - 1); k <= (nowCol + 1); k++) {　//2次元配列のループ（行）

if ((j < 0) || (j > row-1) || (0 > k) || (k > col-1)) { ////もし範囲外ならcontinue
continue;
} else if (charValueArgs[i] == gameboard[j][k]) {　//もしヒットすれば以下の処理

if (work[j][k] == gameboard[j][k]) { //もしそのインデックスの中身が2度目なら以下の処理
blt = false;
i = searchLength + 1;　//ループ処理を全て終了させるため、iの値を範囲外に設定
break LOOP;
} else {　//2度目じゃなければ以下の処理
blt = true;
nowRow = j;
nowCol = k;
work[nowRow][nowCol] = charValueArgs[i]; //使ったインデックスの中身を記録

break LOOP;
}

} else { //ヒットしなければ以下の処理

blt = false;
}
}
}
}

for (int i = 0; i < row; i++) {　//work配列を初期化
for (int j = 0; j < col; j++) {
work[i][j] = ' ';
}
}
return blt;

ここで、iの値が2以上いかないというエラーがでます。例えばAEGPを検索する場合、AEまでしか検索していないみたいなのです
これでは本来falseを返すはずがtrueを返してしまいます
どのように直したらよいでしょうか。ラベルがまずかったでしょうか。
しかし、検索する文字が隣り合っていないとわかった時点でループ全てを一気にbreakして最後のreturnにいきたく、
あるいは文字がヒットした場合、2次元配列のループを最初に戻し、新しい検索対象のためのループにするために、一気にループを２つbreakする方法がわかりませんでした

回答No.4

Tacosan

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

補足

ありがとうございます。先ほど少し変えてみたのですが、２つほエラーがでてしまいます

public class DiceTray {

private char[][] gameboard;
private int row, col;
private char[][] work;

public DiceTray(char[][] array) {
row = array.length;
col = array[0].length;
gameboard = array;
work = new char[row][col];
}

public boolean stringFound(String search) {

boolean blt = true;
int nowRow = 0, nowCol = 0;
int charValueArgsLength = search.length();
char[] charValueArgs = new char[charValueArgsLength];

int searchLength = charValueArgsLength - 1;
search.getChars(0, searchLength, charValueArgs, 0);

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;
}
}
}

work[nowRow][nowCol] = charValueArgs[0];

LOOP: for (int i = 1; i <= searchLength; i++) {

for (int j = (nowRow - 1); j <= (nowRow + 1); j++) {

for (int k = (nowCol - 1); k <= (nowCol + 1); k++) {

if ((j < 0) || (j >= row) || (0 > k) || (k >= col)) {
continue;
} else if (charValueArgs[i] == gameboard[j][k]) {

if (work[nowRow][nowCol] == gameboard[j][k]) {
blt = false;
i = searchLength + 1;
break LOOP;
} else {
blt = true;
nowRow = j;
nowCol = k;
work[nowRow][nowCol] = charValueArgs[i];
break LOOP;
}
} else {
blt = false;
}
}
}
if ((blt == true) && (i == searchLength)) {
return blt;
}
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
work[i][j] = ' ';
}
}
return blt;
}

}

エラーとは、1つ目は、ABAやABBといった同じ文字を2度使う場合trueを返してしまうことと、
2つ目は、DIEといった1文字目と2文字目が隣り合っていない文字の検索の場合期待通りの結果を出すのですが（falseを返す）、
DHFJといった1文字目と2文字目が隣り合った文字の時のfalseを返す場合、trueが返ってきてしまいます。
ラベルを使って少し簡単にしたのですが、どのようにエラーを直せばよいかがわかりません。
どなたかご教授お願いします

回答No.3

Yanch

> 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);
　　}
}

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

補足

お世話になります。自分なりに組んでみたのですが、調べる検索値によってエラーが出てしまいます。
以下のように組んで見ました。ちなみに4×4の中のマスはchar型で、検索する対象はString型なのでchar型に直して検索します

public class DiceTray {

private char[][] gameboard;
private int row, col;
private char[][] work;

public DiceTray(char[][] array) {
row = array.length;
col = array[0].length;
gameboard = array;
work = new char[row][col];
}

public boolean stringFound(String search) {

boolean blt = true;
int r = 0, c = 0, count = 0, count2 = 0;
int length = search.length();
char[] charValue = new char[length];

search.getChars(0, length, charValue, 0); //String型のsearchをchar型の配列に変換

for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (gameboard[i][j] == charValue[0]) {
r = i;
c = j;
count++;
break;
} else {
blt = false;
}
}
if (count > 0)
break;
}

count = 0;
work[r][c] = charValue[0];
for (int i = 1; i < length; i++) {
for (int j = (r - 1); j <= (r + 1); j++) {
for (int k = (c - 1); k <= (c + 1); k++) {
if (j < 0 || j >= row || 0 > k || k >= col) {
continue;
} else if (gameboard[j][k] == charValue[i]) {
if (work[j][k] == charValue[i]) {
System.out.println(j+" "+k+" "+work[j][k]+" "+charValue[i]+" "+i);
count++;
count2++;
blt = false;
break;
} else {
blt = true;
r = j;
c = k;
work[r][c] = charValue[i];
count++;
break;
}
}else{
blt = false;
if(j==r+1 && k==c+1){
count++;
break;
}
}
}
if (count > 0)
break;
}
if(count2>0)
break;
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
work[i][j] = ' ';
}
}
return blt;
}

}

あまりうまくはないと思いますが・・・例えば検索する文字がABAだった場合、これはAが2度使われているのでfalseです。しかしtrueを返してしまいます。
他にDHGFを検索すると、trueを返すはずですがfalseが返ってきます。
ABFEJINMでtrueを返す場合やACBでfalseを返すのはできるのですが、DHGFなどの間違いを直すと今度は動いてたはずのABFEJINMなどの例が間違いになってしまいます。
間違いを何度探してもエラーがでてしまいてづまってしまいました。
どのようになおしたらよいでしょうか？宜しくお願いいたします

ちなみに4×4のマスは以下のをテストクラスから受け取ってきます。
A B C D
E F G H
I J K L
M N O P

回答No.2

osamuy

ちょっくら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さんの回答と似たようなもんだったり。

補足

すみません、rubyはわからないです・・・

回答No.1

Yanch

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

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文を用意するとすごい長さになってしまいます。
そのような印象は受けませんよ。

補足

どうもありがとうございます。質問なのですが、　
if (周りにi文字目の文字があるか？(r, c)) {　←この部分でどう検索したらいいのかがわかりません。
質問欄にも書きましたように、角の検索、端の行列の検索、中の検索で検索範囲が変わり検索方法を変えないといけないように思えます。
ABCGBを検索する場合、Gはその周りの8つの検索になるのでfor文2つを普通に回せば出来ますが、Aの周りのBを検索する時にGと同じやり方をすると配列の範囲外を検索することになってしまいエラーがでます。
同様にBの周りを検索すると、その周りの5つの検索だけでよく、Bより上のインデックスは配列の外になってしまいます。
if (周りにi文字目の文字があるか？(r, c)) {　←このif文の中身は、上であげた角、行列、中、全ての場合の検索をif文で分けてかかないといけないのでしょうか。
すると少々長くなってしまい不恰好かなと思いました。これを短くスマートに出来る方法はありませんでしょうか？