java - 如何遍历二维字符数组在java中搜索单词？

Question

我在完成学校作业时遇到问题，非常希望获得一些见解。我被要求使用 25x25 2d 字符数组创建一个单词搜索，并以某种方式通过开发一种算法来遍历该数组，该算法将搜索该数组以查找 21 个预定义单词。

到目前为止，我已经能够创建一个包含需要查找的单词的参差不齐的数组，以及将字符放置在每个位置的二维数组。

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

}

我在创建算法来搜索二维数组并将其与单词列表中的字符匹配时遇到问题。 我应该采用不同的方法来向前、向后和对角搜索。 我已经努力好几天了，只是为了进行正向搜索。

我真的不知道如何解决这个问题，到目前为止我所知道的是

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 个可能的方向。您可以用一个 vector 来表示每个。例如，“向前”方向将是 (0, 1) (第一个行号，然后是列) - 指向右侧的 vector 。左上角对角线方向为(-1, -1)。反正你懂这个意思。

然后，创建一个函数

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

它可以获取当前矩阵位置((row, col)，单词应该从这里开始)、搜索方向((d_row, d_col))和一个单词寻找。它返回给定的单词是否在这里。
然后您可以针对不同的方向调用它，例如

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 行内包含所有处理代码(输入读取除外)。