как пройти через 2d массив символов для поиска слов в Java? - PullRequest
Новая
       46

как пройти через 2d массив символов для поиска слов в Java?

2 голосов
/ 25 января 2011

У меня проблемы со школьным заданием, и я был бы очень признателен.Меня просят создать поиск слова с использованием 2x-массива 25x25 и каким-то образом пройти по этому массиву, разработав алгоритм, который будет выполнять поиск по нему, чтобы найти 21 предопределенное слово.рваный массив слов, которые мне нужно найти, и массив 2d с символами, размещенными в каждой позиции. 

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

        }
      }
    }
  }
}

}

Любая помощь или указатели будут с благодарностью!

Ответы [ 3 ]

2 голосов
/ 25 января 2011

Хитрость в том, что вам не нужно рассматривать все 8 возможных направлений отдельно. Вы можете представить каждого с вектором. Например, направление «вперед» будет (0, 1) (номер строки, затем столбец) - вектор, указывающий вправо. Диагональное верхнее левое направление будет (-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 строках.

1 голос
/ 25 января 2011

Сначала нужно понять, как искать короткую строку внутри большей строки.Здесь есть несколько вариантов: от самого простого алгоритма до более сложного (например, Кнут Моррис Пратт и его семья).Вы можете получить список их описаний здесь: http://en.wikipedia.org/wiki/String_searching_algorithm. Я настоятельно рекомендую вам сначала попробовать наивный поиск.

Как только вы сможете искать строку внутри другой строки, вам нужно будет абстрагировать способ доступабольшую строку и адаптировать матричные данные к ней.

В основном предполагая эту матрицу: 

   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

, вы сначала создадите некоторый код, чтобы иметь возможность найти abc внутри abcd или bcda или cdab и т. Д.

После того, как вы сможете это сделать, вы должны построить промежуточный этап извлечения (для каждого возможного типа поиска: горизонтального, вертикального, диагонального, обратного диагонального) ряда символов и применить предыдущийалгоритм на них.

Например, если мы хотим выполнить поиск по диагонали, мы сгенерируем 7 строк из матрицы: 

a
bb
ccc
dddd
aaa
bb
c

, если вы хотите выполнить поиск по горизонтали, вы сгенерируете эти строки: 

abcd
bcda
cdab
dabc

и ищите внутри каждой строки.

Как только это сработает, вы должны объединить поиск с чтением правильных символов из матрицы.Надеюсь, если вы пойдете по этому пути, вы сможете понять это:).

Удачи.

0 голосов
/ 04 мая 2012

Чтобы перемещаться по диагонали в любой двумерной матрице произвольных размеров, надеемся, что поможет следующая функция. 

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