-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathB9202.java
More file actions
127 lines (98 loc) · 3.18 KB
/
B9202.java
File metadata and controls
127 lines (98 loc) · 3.18 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
package Practice;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
public class B9202 { //Boggle
static int W, score, found_count;
static String longest_word;
static char[][] board;
static boolean[][] vis;
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
W = Integer.parseInt(br.readLine());
String[] words = new String[W];
for(int i = 0; i < W; i++) words[i] = br.readLine();
br.readLine();
int B = -1;
while(B != 0) {
if(B == -1) B = Integer.parseInt(br.readLine());
else br.readLine();
B--;
score = 0;
longest_word = "";
found_count = 0;
Trie trie = new Trie();
for(int i = 0; i < W; i++) trie.insert(words[i]);
vis = new boolean[4][4];
board = new char[4][4];
for(int i = 0; i < 4; i++) {
String str = br.readLine();
for(int j = 0; j < 4; j++) board[i][j] = str.charAt(j);
}
trie.search();
sb.append(score).append(' ').append(longest_word).append(' ').append(found_count).append('\n');
}
System.out.println(sb);
}
static class Trie {
private TrieNode Node = new TrieNode();
private int[] dx = {1, -1, 0, 0, 1, 1, -1, -1}, dy = {0, 0, 1, -1, 1, -1, 1, -1};
void insert(String str) {
TrieNode node = this.Node;
for(int i = 0; i < str.length(); i++) node = node.childNode.computeIfAbsent(str.charAt(i), key -> new TrieNode());
node.lastNode = true;
}
private void search(TrieNode node, int row, int col, String str) {
node = node.childNode.get(board[row][col]);
if(node == null) return;
if(node.lastNode) {
update(str);
delete(Node, str, 0);
}
for(int i = 0; i < 8; i++) {
int r = row + dx[i];
int c = col + dy[i];
if(r < 0 || c < 0 || r >= 4 || c >= 4 || vis[r][c]) continue;
vis[r][c] = true;
search(node, r, c, str + board[r][c]);
vis[r][c] = false;
}
}
void search() {
for(int i = 0; i < 4; i++) {
for(int j = 0; j < 4; j++) {
vis[i][j] = true;
search(Node, i, j, "" + board[i][j]);
vis[i][j] = false;
}
}
}
private void update(String str) {
found_count++;
if(longest_word.length() < str.length()) longest_word = str;
else if(longest_word.length() == str.length() && longest_word.compareTo(str) > 0) longest_word = str;
if(str.length() == 8) score += 11;
else if(str.length() == 7) score += 5;
else if(str.length() == 6) score += 3;
else if(str.length() == 5) score += 2;
else if(str.length() >= 3) score += 1;
}
private void delete(TrieNode node, String str, int index) {
if(node.lastNode) {
node.lastNode = false;
return;
}
TrieNode tempNode = node;
node = node.childNode.get(str.charAt(index));
if(node == null) throw new Error("Can't Find " + str.charAt(index) + " in Trie");
delete(node, str, index + 1);
if(node.childNode.size() == 0 && !node.lastNode) tempNode.childNode.remove(str.charAt(index));
}
}
static class TrieNode {
HashMap<Character, TrieNode> childNode = new HashMap<>();
boolean lastNode;
}
}