关于JAVA算法的问题！谢谢！！

Question

write a program to find words that are hidden in a square of
letters. Below is an example:

x z v g k u p
g s n i b p k
p i a n o d g
l w c e l l o
b q z h s u a
t b n s g w b
l k r t q f h

Starting from any character in the square, move to the left, to the right, up,
down, or on any of the four diagonals Your task is to find words
that can be spelled out with those characters on the moving path. For example,
you might have found the above square contains the word “viola” starting from
the ‘v’ in the first row to the last character in the fifth row. Similarly, you’ll
find “piano” and “cello”. For “piano”, you may wonder if words “a”, “a”, and
“no”, which are sub-strings of “piano”, count. The answer is yes and no. If a
word is part of another word, both words should be found, for example, “prose”
and “prosecution”. However, we just ignore a word if its length is less than or
equal to 4. In fact, you don’t need to consider the latter restriction, because we
shall provide you a dictionary containing no short words .

[img]/upload/attachment/99946/1104327c-66d0-3745-bc7a-5c104b0c508d.jpg[/img]

Thanks !!

(注:您只需提供具体算法或者分析的思路！谢谢~)

Answer 1

[code="java"]
package sny.ag;

public class WordCross {
private static char[][] charMap = {
{'x', 'z', 'v', 'g', 'k', 'u', 'p'},
{'g', 's', 'n', 'i', 'b', 'p', 'k'},
{'p', 'i', 'a', 'n', 'o', 'd', 'g'},
{'l', 'w', 'c', 'e', 'l', 'l', 'o'},
{'b', 'q', 'z', 'h', 's', 'u', 'a'},
{'t', 'b', 'n', 's', 'g', 'w', 'b'},
{'l', 'k', 'r', 't', 'q', 'f', 'h'}
};

private static String[] wordSet = {
    "acz",
    "ce",
    "cel",
    "kpg",
    "krt"
};

public static void main(String[] args) {
    int wordLen = wordSet.length - 1;
    for (int x = 0; x < 7; x++) {
        for (int y = 0; y < 7; y++) {
            search(x, y, 0, 1, 0, 0, wordLen, new StringBuffer());
            search(x, y, 1, 1, 0, 0, wordLen, new StringBuffer());
            search(x, y, 1, 0, 0, 0, wordLen, new StringBuffer());
            search(x, y, -1, 1, 0, 0, wordLen, new StringBuffer());
            search(x, y, 0, -1, 0, 0, wordLen, new StringBuffer());
            search(x, y, -1, -1, 0, 0, wordLen, new StringBuffer());
            search(x, y, -1, 0, 0, 0, wordLen, new StringBuffer());
            search(x, y, -1, 1, 0, 0, wordLen, new StringBuffer());
        }
    }

// search(0, 0, 0, 1, 0, 0, 1, new StringBuffer());
}

private static void search(int x, int y, int dx, int dy, int p, int s, int e, StringBuffer str) {
    char c = charMap[x][y];
    str.append(c);
    int s1 = -1, e1 = -1;
    for (int i = s; i <= e; i++) {
        if (wordSet[i].length() > p && wordSet[i].charAt(p) == c) {
            s1 = i;
            break;
        }
    }
    if (s1 == -1) {
        return;
    }
    for (int i = s1; i <= e; i++) {
        if (wordSet[i].length() > p) {
            if (wordSet[i].charAt(p) == c) {
                e1 = i;
                if (wordSet[i].length() == str.length()) {
                    System.out.println(str + "[" + x + "," + y + "][" + dx + "," + dy + "]");
                }
            } else {
                break;
            }
        }
    }
    x += dx;
    y += dy;
    if (x >= 0 && y >= 0 && x < 7 && y < 7) {
        search(x, y, dx, dy, p + 1, s1, e1, str);
    }
}

}
[/code]

不保证速度，应该使用更有效的搜索策略。另外字典也应该使用其它方式存储。
只是演示一下想法而已。