s*******n
发帖数: 97 | 1 题目2：
boggle puzzle 找到里面所有的单词，写code
DFS? | g*********e
发帖数: 14401 | | s*******n
发帖数: 97 | | g**********y
发帖数: 14569 | 4 public class Boggle {
private final int N = 5;
private HashSet m_words;
public Boggle() {
m_words = new HashSet();
}
public static void main(String[] args) {
String[] str = new String[]{
"AEBOF", "TSUVW", "RFOEG", "RSOFI", "PQWRE"
};
new Boggle().run(str);
}
public void run(String[] str) {
char[][] cs = new char[N][N];
boolean[][] used = new boolean[N][N];
m_words.clear();
Trie trie = new Trie();
String dictionary = FileHelper.readFile("src/test/resources/english-
dict.txt");
for (String word : dictionary.split("\n")) {
if (word.length() > 0) trie.addWord(word.toLowerCase());
}
for (int i=0; i
cs[i] = str[i].toLowerCase().toCharArray();
}
for (int i=0; i
for (int j=0; j
dfs("", cs, i, j, used, trie);
}
}
System.out.println("Find " + m_words.size() + " words.");
}
private void dfs(String cur, char[][] cs, int i, int j, boolean[][] used
, Trie node) {
if (i<0 || i>N-1 || j<0 || j>N-1 || used[i][j]) return;
String next = cur + cs[i][j];
node = node.getNode(cs[i][j]);
if (node == null) return;
used[i][j] = true;
if (node.isWord() && !m_words.contains(next)) {
m_words.add(next);
System.out.println(next);
}
dfs(next, cs, i-1, j-1, used, node);
dfs(next, cs, i, j-1, used, node);
dfs(next, cs, i+1, j-1, used, node);
dfs(next, cs, i-1, j, used, node);
dfs(next, cs, i+1, j, used, node);
dfs(next, cs, i-1, j+1, used, node);
dfs(next, cs, i, j+1, used, node);
dfs(next, cs, i+1, j+1, used, node);
used[i][j] = false;
}
} | l*****a
发帖数: 14598 | 5 a little optimization
for(int m=-1;m<=1;m++)
for(int n=-1;n<=1;n++)
{
if(m==0&&n==0)continue;
dfs(...,i+m,j+n,,,,,);
}
【在 g**********y 的大作中提到】
: public class Boggle {
: private final int N = 5;
: private HashSet m_words;
:
: public Boggle() {
: m_words = new HashSet();
: }
:
: public static void main(String[] args) {
: String[] str = new String[]{
| f*******t
发帖数: 7549 | 6 #include
#include
#include
#define ENTRYNOTFOUND 0
#define ENTRYFOUND 1
#define NOTCOMPLETE 2
struct Trie;
void FindWords(Trie *root);
struct Trie
{
Trie();
~Trie();
Trie *children[26];
bool isEnd;
};
Trie::Trie()
{
for(int i = 0; i < 26; i++)
children[i] = NULL;
isEnd = false;
}
Trie::~Trie()
{
for(int i = 0; i < 26; i++) {
if(children[i]) {
delete children[i];
children[i] = NULL;
}
}
}
void TrieInsert(Trie *root, const char *str)
{
if(!str || *str < 'a' || *str > 'z') {
printf("Invalid line\n");
return;
}
Trie *cur = root;
while(*str >= 'a' && *str <= 'z') {
int index = (int)(*str - 'a');
if(cur->children[index] == NULL) {
cur->children[index] = new Trie();
}
cur = cur->children[index];
str++;
}
if(cur != root)
cur->isEnd = true;
}
int TrieSearch(Trie *root, const char *str)
{
if(!str || *str < 'a' || *str > 'z') {
printf("Invalid string!\n");
return ENTRYNOTFOUND;
}
printf("Looking for word %s\n", str);
Trie *cur = root;
while(*str >= 'a' && *str <= 'z') {
int index = (int)(*str - 'a');
if(cur->children[index]) {
cur = cur->children[index];
str++;
}
else
return ENTRYNOTFOUND;
}
if(cur != root && cur->isEnd)
return ENTRYFOUND;
else
return NOTCOMPLETE;
}
int main()
{
Trie *root = new Trie();
FILE *fp = fopen("dictionary.txt", "r");
if(!fp) {
printf("Cannot find dictionary file\n");
exit(-1);
}
char buff[32];
int count = 0;
while(fgets(buff, 31, fp) != NULL) {
TrieInsert(root, buff);
memset(buff, 0, 32);
count++;
}
fclose(fp);
printf("Loaded %d words\n", count);
FindWords(root);
delete root;
return 0;
}
#define WIDTH 4
#define HEIGHT 4
bool isValidIndex(int x, int y, bool used[HEIGHT][WIDTH])
{
if(x >= 0 && x < WIDTH && y >= 0 && y < HEIGHT && !used[y][x])
return true;
else
return false;
}
void dfsWord(Trie *root, char *buff, int buffidx, char matrix[HEIGHT][WIDTH]
, bool used[HEIGHT][WIDTH], int x, int y)
{
/*
if(buffidx > 0)
printf("Current buffer: %s\n", buff);
*/
buff[buffidx] = matrix[y][x];
used[y][x] = true;
int status = TrieSearch(root, buff);
if(status != ENTRYNOTFOUND) {
if(status == ENTRYFOUND)
printf("Found word: %s\n", buff);
if(isValidIndex(x-1, y, used))
dfsWord(root, buff, buffidx+1, matrix, used, x-1, y);
if(isValidIndex(x-1, y-1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x-1, y-1);
if(isValidIndex(x, y-1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x, y-1);
if(isValidIndex(x+1, y-1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x+1, y-1);
if(isValidIndex(x+1, y, used))
dfsWord(root, buff, buffidx+1, matrix, used, x+1, y);
if(isValidIndex(x+1, y+1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x+1, y+1);
if(isValidIndex(x, y+1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x, y+1);
if(isValidIndex(x-1, y+1, used))
dfsWord(root, buff, buffidx+1, matrix, used, x-1, y+1);
}
buff[buffidx] = 0;
used[y][x] = false;
}
void FindWords(Trie *root)
{
char matrix[HEIGHT][WIDTH] = {
{'t', 'e', 'g', 's'},
{'r', 'e', 'i', 't'},
{'n', 'i', 'f', 'o'},
{'g', 'l', 'k', 'c'},
};
bool used[HEIGHT][WIDTH];
for(int i = 0; i < HEIGHT; i++) {
for(int j = 0; j < WIDTH; j++) {
used[i][j] = false;
}
}
int tempx, tempy;
char buff[32];
int buffidx;
bool noValidChoice;
for(int y = 0; y < HEIGHT; y++) {
for(int x = 0; x < WIDTH; x++) {
memset(buff, 0, 32);
buffidx = 0;
dfsWord(root, buff, buffidx, matrix, used, x, y);
}
}
} | s*******n
发帖数: 97 | 7 both solution and optimization are nice...thanks..
【在 l*****a 的大作中提到】
: a little optimization
: for(int m=-1;m<=1;m++)
: for(int n=-1;n<=1;n++)
: {
: if(m==0&&n==0)continue;
: dfs(...,i+m,j+n,,,,,);
: }
| s*******n
发帖数: 97 | 8 good to learn..thanks..
【在 f*******t 的大作中提到】
: #include
: #include
: #include
: #define ENTRYNOTFOUND 0
: #define ENTRYFOUND 1
: #define NOTCOMPLETE 2
: struct Trie;
: void FindWords(Trie *root);
: struct Trie
: {
|
|
