BOJ. Boggle (9202)

[Link] https://www.acmicpc.net/problem/9202

#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;
}