how to traverse though a 2d char array searching for words in java?

I am having trouble with a school assignment and would really appreciate some insight. I am asked to create a wordsearch using a 25x25 2d char array and somehow go through that array by developing an algorithm that will search through it to find 21 pre-defined words.

So far I have been able to create a ragged array of the words that I need to find and the 2d array with the chars placed in each position.

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

wor开发者_Go百科dlist = 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();

}

My problem in creating the algorithm to search though the 2d array and match it with a character in the wordlist. I am supposed to make different methods, for searching forwards, backwards and diagonal. I have been struggling for days just to do the forward search.

I really how no idea about how to go about this problem, so far all I have is

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

        }
      }
    }
  }
}    

}

Any help or pointers would be greatly appreciated!

---

The trick is, you don't need to consider all 8 possible directions separately. You can represent each with a vector. E.g., 'forward' direction would be (0, 1) (first row number, then column) - a vector pointing to the right. Diagonal top-left direction would be (-1, -1). Well, you get the idea.

Then, just create a function

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

It can take current matrix position ((row, col), where word is supposed to start), search direction ((d_row, d_col)) and a word to look for. It returns whether the given word is here.
Then you can invoke it for different directions, e.g.

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

(I'm listing them in clock-wise order)

Implementing findWord is just incrementing current position by d_row and d_col, until we find mismatch in characters or word ends. The basic routine is like this

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

I bet you'll have all processing code (except input-reading) in 40 lines.

---

You first need to understand how to search a short string inside a bigger string. There are couple of options here: from the simplest algorithm up to more complex (like Knuth Morris Pratt and the family). You can get a list of their descriptions here: http://en.wikipedia.org/wiki/String_searching_algorithm. I strongly recommend you try the naive search first.

Once you can search a string inside another string you will need to abstract the way you access the bigger string and adapt the matrix data to it.

Basically assuming this matrix:

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

and this string abc

you will first make some code to be able to find abc inside abcd or bcda or cdab etc.

Once you can do that you should build the intermediate step of extracting (for each possible lookup type: horizontal, vertical, diagonal, reverse diagonal) series of chars and apply the previous algorithm on them.

For example if we want to search diagonally we would generate 7 strings from the matrix:

a
bb
ccc
dddd
aaa
bb
c

if you want to search horizontally you would generate those strings:

abcd
bcda
cdab
dabc

and seach inside each string.

Once this is working you should combine the searching with reading the proper chars from the matrix. Hopefully if you follow this path you will be able to figure it out :).

Good luck.

---

To travel diagonally in any 2D matrix of arbitrary dimensions, hope the below function helps.

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