[Link] https://www.acmicpc.net/problem/9202
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
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cstring>
// #include <bits/stdc++.h>
using namespace std;
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i < n; i++)
#define fori(s, e) for(int i = s; i < e; i++)
#define endl "\n"
#define nulls '\0'
#define dkdk " "
struct trie{
trie *tries[26];
string orig_str;
bool last = false;
int len;
trie() { memset(tries, 0, sizeof(tries)); }
~trie() { fori(0, 26) delete tries[i]; }
void insert(string str, int idx) {
if(str.size() == idx) {
this->last = true;
this->len = str.size();
this->orig_str = str;
return;
}
int char_code = str[idx] - 'A';
if(this->tries[char_code] == NULL) this->tries[char_code] = new trie();
this->tries[char_code]->insert(str, idx + 1);
}
bool search(char* cptr) {
trie* t = this;
while(*cptr != nulls) {
if(t -> tries[*cptr-'A'] == NULL) return false;
t = t -> tries[*cptr-'A'];
cptr++;
}
return t->last;
}
};
typedef long long ll;
const int INF = 987654321;
const int MAX = 123456;
const int log = 17;
int n, w, b, score;
char board[4][4];
bool visit[4][4];
int di[8] = { -1, 0, 1, 0, 1, -1, 1, -1 };
int dj[8] = { 0, 1, 0, -1, 1, -1, -1, 1 };
map<string, bool> counted;
string longest_word;
int cnt = 0;
trie t;
int to_score(int len) {
if(len < 3) return 0;
if(len < 5) return 1;
if(len < 6) return 2;
if(len < 7) return 3;
if(len < 8) return 5;
return 11;
}
void dfs(int ci, int cj, trie *ct) {
if(ct -> tries[board[ci][cj]-'A'] == NULL) return;
ct = ct -> tries[board[ci][cj] - 'A'];
if(ct -> last && !counted[ct->orig_str]) {
counted[ct->orig_str] = true;
if(longest_word.size() < ct->orig_str.size()) longest_word = ct->orig_str;
else if(longest_word.size() == ct->orig_str.size()) {
if(longest_word > ct -> orig_str) longest_word = ct->orig_str;
}
cnt++;
score += to_score(ct -> len);
}
for0(i, 8) {
int ai = ci + di[i], aj = cj + dj[i];
if(ai < 0 || aj < 0 || ai >=4 || aj >=4) continue;
if(visit[ai][aj]) continue;
visit[ai][aj] = true;
dfs(ai, aj, ct);
visit[ai][aj] = false;
}
}
void solve() {
for0(i, 4) {
for0(j, 4) {
visit[i][j] = true;
dfs(i, j, &t);
visit[i][j] = false;
}
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("input.txt", "r", stdin);
cin >> w;
for0(i, w) {
string word; cin >> word;
t.insert(word, 0);
counted.insert({ word, false });
}
cin >> b;
for0(i, b) {
for0(j, 4) for0(k, 4) cin >> board[j][k];
for(auto iter = counted.begin(); iter!=counted.end(); iter++)
iter->second = false;
score = cnt = 0;
longest_word = "";
solve();
cout << score << dkdk << longest_word << dkdk << cnt << endl;
}
return 0;
}