2

文字列として 2D 配列が与えられ、キーボードから単語が与えられます。単語はどのようなものでもかまいません (8 つの隣接語すべてが考慮されます) が、一致中に同じ文字を 2 回使用することはできません。単語の最初と最後の文字のインデックスを (x,y) として返します。一致が見つからない場合は -1 を返します。

それが問題です。検索に困っています。私はそれを試しました：

int x=0,y=0;
            for(int f=0; f<WordinArray.length; f++){
                for(int i=0; i<matrix.length; i++){
                    for(int j=0; j<matrix[0].length; j++){
                        if(matrix[i][j].equals(WordinArray[f])){
                            x=i; y=j;
                            System.out.print("("+x+","+y+")");

                        }
                    }
                }
            }

しかし、そのコードは想定どおりに機能していません。この検索コードを他にどのように書くことができますか?

4

4 に答える 4

2

私があなたの質問を正しく理解していれば。これは私が今作った簡単な答えです。

int H = matrix.length;
int W = matrix[0].length;
int xStart = -1, yStart = -1;
int xEnd = -1, yEnd = -1;

String word = "WordLookingFor".toLowerCase();

for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
        if (matrix[i][j] == word.charAt(0)) {
            int tempxStart = i;
            int tempyStart = j;
            for (int x = -1; x <= 1; x++) {
                for (int y = -1; y <= 1; y++) {
                    for (int k = 0; k < word.length(); k++) {
                        int xx = i+x*k;
                        int yy = j+y*k;
                        if(xx >= 0 && xx < H && yy >= 0 && yy < W && (x != 0 || y != 0)) {
                            if(matrix[xx][yy] != word.charAt(k))
                                break;
                            else if (matrix[xx][yy] == word.charAt(k) && k == word.length()-1) {
                                xStart = tempxStart;
                                yStart = tempyStart;
                                xEnd = xx;
                                yEnd = yy;
                            }
                        } else
                            break;
                    }
                }
            }
        }
    }
}

8 個の近隣すべてをチェックするために使用したちょっとしたトリックは、2 つの for ループを使用して、すべての方向を作成することです。

for (int x = -1; x <= 1; x++) {
    for (int y = -1; y <= 1; y++) {
        if(x !=0 || y != 0)
            System.out.println(x + ", " + y);
    }
}

これにより、

-1, -1
-1, 0
-1, 1
0, -1
0, 1
1, -1
1, 0
1, 1

注意: 0,0 以外のすべて (同じセルに再度アクセスする必要はありません)。コードの残りの部分は、完全な一致が見つかる (または見つからない可能性がある) まで、文字のマトリックスと、探している単語の全長を単純にトラバースするだけです。

于 2013-11-14T21:49:53.067 に答える
2

Sixie のコードを参照する

これがあなたのプログラムへの有効な入力/出力であると仮定しますか?

Size:
4x4
Matrix:
a b c d
e f g h
i j k l
m n o p
Word: afkp
(0,0)(3,3)

このフォームの入力で機能するようにコードを編集しました (現時点では大文字と小文字が区別されますが、設定によって簡単に変更できます.toLowerCase()

Scanner k = new Scanner(System.in);
System.out.println("Size: ");
String s = k.nextLine();
s.toUpperCase();

int Xindex = s.indexOf('x');
int x = Integer.parseInt(s.substring(0, Xindex));
int y = Integer.parseInt(s.substring(Xindex + 1));

System.out.println("Matrix:");
char[][] matrix = new char[x][y];

for (int i = 0; i < x; i++) {
    for (int p = 0; p < y; p++) {
        matrix[i][p] = k.next().charAt(0);
    }
}

System.out.print("Word: ");
String word = k.next();

int xStart = -1, yStart = -1;
int xEnd = -1, yEnd = -1;

// looping through the matrix
for (int i = 0; i < x; i++) {
    for (int j = 0; j < y; j++) {
        // when a match is found at the first character of the word
        if (matrix[i][j] == word.charAt(0)) {
            int tempxStart = i;
            int tempyStart = j;
            // calculating all the 8 normals in the x and y direction
            // (the 8 different directions from each cell)
            for (int normalX = -1; normalX <= 1; normalX++) {
                for (int normalY = -1; normalY <= 1; normalY++) {
                    // go in the given direction for the whole length of
                    // the word
                    for (int wordPosition = 0; wordPosition < word
                            .length(); wordPosition++) {
                        // calculate the new (x,y)-position in the
                        // matrix
                        int xPosition = i + normalX * wordPosition;
                        int yPosition = j + normalY * wordPosition;
                        // if the (x,y)-pos is inside the matrix and the
                        // (x,y)-vector normal is not (0,0) since we
                        // dont want to check the same cell over again
                        if (xPosition >= 0 && xPosition < x
                                && yPosition >= 0 && yPosition < y
                                && (normalX != 0 || normalY != 0)) {
                            // if the character in the word is not equal
                            // to the (x,y)-cell break out of the loop
                            if (matrix[xPosition][yPosition] != word
                                    .charAt(wordPosition))
                                break;
                            // if the last character in the word is
                            // equivalent to the (x,y)-cell we have
                            // found a full word-match.
                            else if (matrix[xPosition][yPosition] == word
                                    .charAt(wordPosition)
                                    && wordPosition == word.length() - 1) {
                                xStart = tempxStart;
                                yStart = tempyStart;
                                xEnd = xPosition;
                                yEnd = yPosition;
                            }
                        } else
                            break;
                    }
                }
            }
        }
    }
}
System.out.println("(" + xStart + "," + yStart + ")(" + xEnd + ","
        + yEnd + ")");
k.close();
于 2013-11-16T01:07:40.623 に答える
2

コードを書き始める前に、アルゴリズムをもう少し慎重に計画する必要があると思います。もし私がそれをしていたら、私のアルゴリズムは次のようになるかもしれません。

(1) 単語の最初の文字を探して、配列を反復処理します。

(2) 最初の文字を見つけるたびに、8 つの隣接文字をすべてチェックして、2 番目の文字があるかどうかを確認します。

(3) 最初の文字の隣にある 2 番目の文字を見つけるたびに、配列内の文字に沿って反復し、正しい方向に移動し、各文字を単語と照合します。

(4) 単語全体に一致した場合は、一致を見つけた場所を出力して終了します。

(5) グリッドの端に到達した場合、または一致しない文字が見つかった場合は、ループ (2) の次の繰り返しに進みます。

アルゴリズムを明確にしたら、各ステップをコードに変換する方法を考えます。

于 2013-11-14T21:22:40.277 に答える
0

今回の問題は、単語の最初と最後の文字のインデックスをどのように出力できるかということです。各単語を検索した後に印刷するなど、さまざまな方法を試しました。しかし、それらはすべて機能しませんでした。私は爆破しようとしています。

int[] values = new int[2];
                for(int i=0; i<matrix.length; i++){
                    for(int j=0; j<matrix[0].length; j++){

                        if(Character.toString(word.charAt(0)).equals(matrix[i][j]) == true || Character.toString(ReversedWord.charAt(0)).equals(matrix[i][j]) == true ){
                            System.out.print("("+ i + "," +j+")");
                            //First letter is found.Continue.
                        for(int p=1; p<word.length(); p++){

                        try{
                            for (int S = -1; S <= 1; S++) {
                                for (int SS = -1; SS <= 1; SS++) {
                                    if(S !=0 || SS != 0)
                                        if(matrix[i+S][j+SS].equals(Character.toString(word.charAt(p))) && blocksAvailable[i+S][j+SS] == true || 
                                            matrix[i+S][j+SS].equals(Character.toString(ReversedWord.charAt(p))) && blocksAvailable[i+S][j+SS] == true) {
                                                values[0] = i+S;
                                                values[1] = j+SS;
                                                blocksAvailable[i+S][j+SS] = false;


                                        }
                                }
                            }
                        }catch (ArrayIndexOutOfBoundsException e) {}
于 2013-11-15T18:26:46.163 に答える