Courseraプリンストン大学のアルゴリズムの下でWeek 4:Bogggaleは字をつづり合わせて遊びます.
タスクリンク:http://coursera.cs.princeton.edu/algs4/assignments/boggle.html
今回の任務は実現する必要がある方法が少ないです.今回の任務を完成するには、構想を整理し、より多くの私有方法を実現する必要があります.
単語ツリーを自分で設計する必要があります.単語ツリーの各文字ノードをクラスと定義します.
また、隣接ノードの下付きカテゴリを格納するように設計し、パネル内に隣接する8つの(最大)方向の文字の下付き文字を格納し、実際の配列の長さをnでマークする.
まず、与えられた単語集のために単語ツリーを設計する必要があります.
そしてパネルの文字に対してDFS方式を用いて文字列を構成して単語ツリーを検索する.単語ツリーの葉っぱノードを調べたら、今回の検索は中止します.前のDFSと異なる場合は、マーカー配列を処理する際に、再帰的検索を終了する前に、他の単語のシーケンスがその文字を含むように位置markをfalseに設定する必要がある.
ここでは時間を節約するために、各位置に隣接する文字の下付き文字を事前に計算する必要があります.上のAdjacent類を利用します.
今回の任務は実現する必要がある方法が少ないです.今回の任務を完成するには、構想を整理し、より多くの私有方法を実現する必要があります.
単語ツリーを自分で設計する必要があります.単語ツリーの各文字ノードをクラスと定義します.
private static class Node //
{
private boolean isWord; //
private Node[] next = new Node[R]; //
}また、隣接ノードの下付きカテゴリを格納するように設計し、パネル内に隣接する8つの(最大)方向の文字の下付き文字を格納し、実際の配列の長さをnでマークする.
private static class Adjacent //
{
private int n = 0; //
private int[] neighbor = new int[8]; //
}まず、与えられた単語集のために単語ツリーを設計する必要があります.
そしてパネルの文字に対してDFS方式を用いて文字列を構成して単語ツリーを検索する.単語ツリーの葉っぱノードを調べたら、今回の検索は中止します.前のDFSと異なる場合は、マーカー配列を処理する際に、再帰的検索を終了する前に、他の単語のシーケンスがその文字を含むように位置markをfalseに設定する必要がある.
ここでは時間を節約するために、各位置に隣接する文字の下付き文字を事前に計算する必要があります.上のAdjacent類を利用します.
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.SET;
import edu.princeton.cs.algs4.StdOut;
public class BoggleSolver
{
private static final int R = 26; // A-Z
private boolean[][] marked; //
private char[][] boardChar; //
private Adjacent[] adjacents; //
private int row; //
private int col; //
private Node root; //
private static class Node //
{
private boolean isWord; //
private Node[] next = new Node[R]; //
}
private static class Adjacent //
{
private int n = 0; //
private int[] neighbor = new int[8]; //
}
// 。
// （ A Z）。
public BoggleSolver(String[] dictionary)
{
if (dictionary == null)
throw new java.lang.IllegalArgumentException("the string[] is null");
//
for (int i = 0; i < dictionary.length; i++)
addToDictionary(dictionary[i]);
}
//
private void addToDictionary(String word)
{
if (word == null)
throw new java.lang.IllegalArgumentException("the string is null");
root = add(root, word, 0);
}
//
private Node add(Node x, String word, int d)
{
if (x == null)
x = new Node();
if (d == word.length()) // ，
x.isWord = true;
else {
char c = word.charAt(d);
x.next[c - 'A'] = add(x.next[c - 'A'], word, d + 1);
}
return x;
}
//
private boolean contains(String word)
{
if (word == null)
throw new java.lang.IllegalArgumentException("the word is null");
Node x = get(root, word, 0);
if (x == null)
return false;
else
return x.isWord;
}
//
// null，
private Node get(Node node, String word, int d)
{
if (node == null) //
return null;
else {
if (d < word.length()) { //
char c = word.charAt(d);
return get(node.next[c - 'A'], word, d + 1);
}
else
return node;
}
}
// BogGrand ， 。
public Iterable getAllValidWords(BoggleBoard board)
{
if (board == null)
throw new java.lang.IllegalArgumentException("the board is null");
//
if (row != board.rows() || col != board.cols())
{
row = board.rows(); //
col = board.cols(); //
marked = new boolean[row][col]; //
boardChar = new char[row][col]; //
computeAdj(); //
}
for (int i = 0; i < row; i++) //
for (int j = 0; j < col; j++) //
boardChar[i][j] = board.getLetter(i, j); //
SET words = DFS();
return words;
}
//
private void computeAdj()
{
adjacents = new Adjacent[row * col]; //
for (int i = 0; i < row; i++) { //
for (int j = 0; j < col; j++) { //
int index = i * col + j;
adjacents[index] = new Adjacent(); // adj[index].neineighbor[k]
if (i > 0) //
{
//
if (j > 0)
adjacents[index].neighbor[adjacents[index].n++] = (i - 1) * col + j - 1;
//
adjacents[index].neighbor[adjacents[index].n++] = (i - 1) * col + j;
//
if (j < col -1)
adjacents[index].neighbor[adjacents[index].n++] = (i - 1) * col + j + 1;
}
//
if (j < col -1)
adjacents[index].neighbor[adjacents[index].n++] = i * col + j + 1;
if (i < row -1) //
{
//
if (j < col -1) {
adjacents[index].neighbor[adjacents[index].n++] = (i + 1) * col + j + 1;
}
//
adjacents[index].neighbor[adjacents[index].n++] = (i + 1) * col + j;
//
if (j > 0)
adjacents[index].neighbor[adjacents[index].n++] = (i + 1) * col + j - 1;
}
//
if (j > 0)
adjacents[index].neighbor[adjacents[index].n++] = i * col + j - 1;
}
}
}
//
private SET DFS()
{
SET words = new SET<>(); //
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++)
DFS(i, j, new StringBuilder(), words, root);
return words;
}
//
private void DFS(int indexi, int indexj, StringBuilder pre, SET words, Node node)
{
char c = boardChar[indexi][indexj];
Node next = node.next[c - 'A'];
if (c == 'Q' && next != null)
next = next.next['U' - 'A'];
if (next == null)
return;
if (c == 'Q') // QU
pre.append("QU");
else
pre.append(c);
String string = pre.toString();
if (pre.length() > 2 && next.isWord) //
words.add(string);
marked[indexi][indexj] = true;
for (int i = 0; i < adjacents[indexi * col + indexj].n; i++) {
int indexk = adjacents[indexi * col + indexj].neighbor[i]; //
int indexrow = indexk / col; //
int indexcol = indexk % col; //
if (!marked[indexrow][indexcol])
DFS(indexrow, indexcol, new StringBuilder(pre), words, next);
}
marked[indexi][indexj] = false; //
}
// ， 。
// （ A Z）。
public int scoreOf(String word)
{
if (word == null)
throw new java.lang.IllegalArgumentException("the word is null");
if (!contains(word))
return 0;
if (word.length() <= 2)
return 0;
else if (word.length() <= 4)
return 1;
else if (word.length() == 5)
return 2;
else if (word.length() == 6)
return 3;
else if (word.length() == 7)
return 5;
else
return 11;
}
public static void main(String[] args) {
In in = new In(args[0]);
String[] dictionary = in.readAllStrings();
BoggleSolver solver = new BoggleSolver(dictionary);
BoggleBoard board = new BoggleBoard(args[1]);
int score = 0;
for (String word : solver.getAllValidWords(board)) {
StdOut.println(word);
score += solver.scoreOf(word);
}
StdOut.println("Score = " + score);
}
}