Javaの単語を検索する2dのchar配列をトラバースする方法は？

Question

私は学校の割り当てに問題があり、本当にいくつかの洞察に感謝するでしょう。 25x25の2次元文字配列を使ってwordsearchを作成するように求められ、21の事前定義された単語を検索するアルゴリズムを開発することによって、何とかその配列を調べます。

これまで私は見つけ出す必要がある単語の不揃いな配列と、各位置に配置された文字を持つ2次元配列を作成することができました。

in = new ASCIIDataFile("wordsearch.txt"); 
display = new ASCIIDisplayer(); 
int numberWords = in.readInt(); 

wordlist = new char[numberWords][]; 

for (int i =0; i<wordlist.length; i++){ 
    wordlist[i] = in.readLine().toUpperCase().toCharArray(); 
} 
for(int i = 0;i<wordlist.length; i++){ 
    display.writeLine(" "); 
    for(int j = 0;j<wordlist[i].length; j++){ 
    display.writeChar(wordlist[i][j]); 
    } 
} 
//done wordlists 

int gridLength = in.readInt(); 
int gridHeight = in.readInt(); 

grid = new char[gridHeight][gridLength]; 

for(int i = 0;i<gridLength; i++){ 
    grid[i] = in.readLine().toCharArray(); 

} 

2d配列を検索してワードリスト内の文字と一致させるアルゴリズムを作成する際に問題があります。 私は、前方、後方、斜め方向の検索のために、異なるメソッドを作成することになっています。 私は数日間、前方探索をするだけで苦労してきました。この問題については移動する方法についてのアイデアは、これまでのところ、私が持っているすべては、すべてのヘルプやポインタをいただければ幸いです

for(int k = 0; k<wordlist.length; k++){ 
    int p = 0; 
    for(int row = 0;row<gridLength; row++){ 
    for(int col = 0;col<gridHeight; col++){ 

     while(p<wordlist[k].length){ 
     if(grid[row][col] == wordlist[k][p]){ 

      //do something 

     } 
     } 
    } 
    } 
}  

}ではありません、私は本当にどのように

！

Answer 1

トリックは、8つの可能な方向をすべて個別に検討する必要はありません。それぞれをベクトルで表現することができます。たとえば、「前方」の方向は(0, 1)（最初の行番号、次に列） - 右側を指すベクトルです。斜めの左上方向は(-1, -1)となります。さて、あなたはそのアイデアを得る。

すると、ちょうどそれが現在の行列位置（ワードがスタートすることになっている(row, col)、）、検索方向（(d_row, d_col)）とを探すために言葉を取ることができ

boolean findWord(int row, int col, int d_row, int d_col, char[] word); 

関数を作成します。指定された単語がここにあるかどうかを返します。
その後、さまざまな方向で呼び出すことができます（例：

findWord(row, col, -1, 0, word); 
findWord(row, col, -1, 1, word); 
findWord(row, col, 0, 1, word); 
... 

私たちは文字や単語の両端でのミスマッチを見つけるまで（私は時計回り順に一覧表示しています）findWordの実装

はちょうど、d_rowとd_colにより現在位置を増加しています。基本ルーチンは次のようなものです

while (row < total_rows && row >= 0 && col < total_columns && col >= 0) { 
    // check character here 
    ... 
    row += d_row; 
    col += d_col; 
} 

私は40行ですべての処理コード（入力読み取りを除く）を使用します。

Answer 2

まず、大きな文字列の中の短い文字列を検索する方法を理解する必要があります。ここではいくつかのオプションがあります：最も単純なアルゴリズムからより複雑なものまで（Knuth Morris Prattや家族のように）その説明のリストはhttp://en.wikipedia.org/wiki/String_searching_algorithmで入手できます。私は強くお勧めします。

他の文字列内の文字列を検索することができたら、大きな文字列にアクセスする方法を抽象化し、それに行列データを適合させる必要があります。

は、基本的にこの行列と仮定すると：あなたが最初のいくつかのコードは、などabcdまたはbcdaまたはcdab

内abcを見つけることができるようになります

1 2 3 4 
    ------- 
1| a b c d 
2| b c d a 
3| c d a b 
4| d a b c 

と、この文字列abcをあなた一度（水平、垂直、対角、逆対角）一連の文字を抽出する（それぞれの可能な検索タイプに対して）抽出する中間ステップを構築し、それらの前のアルゴリズム。例えば

我々は斜めに、我々は、マトリックスから7列生成されます検索したい場合：

a 
bb 
ccc 
dddd 
aaa 
bb 
c 

をあなたが水平に検索したい場合は、それらの文字列を生成します：

abcd 
bcda 
cdab 
dabc 

と内部さがします各文字列。

これが機能したら、マトリックスと適切な文字を読み取って検索を組み合わせる必要があります。うまくいけば、あなたがこの道に従えば、あなたはそれを理解することができるでしょう:)。

幸運。

Answer 3

任意の次元の任意の2Dマトリックスで対角線方向に移動するには、以下の関数が役立つことを願ってください。

public static void prinDiagonalsInGrid(char[][] grid, int rows, int cols) 
{ 
    String result = ""; 
    int min = Math.min(rows, cols); 
    int max = Math.max(rows, cols); 

    int sameLengthDiagonals = max - min + 1; 
    int totalDiagonals = (rows + cols) - 1; 

    for (int p = 0; p < totalDiagonals; p++) 
    { 
     int xIndex; 
     int maxCnt; 

     if (p < (min - 1)) // First diagonals 
     { 
      maxCnt = xIndex = p; 
     } 
     // diagonals of equal length in the middle 
     else if (sameLengthDiagonals != 0 && 
       p >= (min - 1) && p < (sameLengthDiagonals + min - 1)) 
     { 
      if (rows < cols) 
       xIndex = rows - 1; 
      else 
       xIndex = p; 
      maxCnt = min - 1; 
     } 
     else // Last diagonals 
     { 
      xIndex = rows - 1; 
      maxCnt = totalDiagonals - p - 1; 
     } 

     for (int cnt = 0; cnt <= maxCnt; cnt++) 
     { 
      result += grid[xIndex][p - xIndex] + " "; 
      --xIndex; 
     } 
     result += "\n"; 
    } 
    System.out.println(result); 
}