BOJ13502: 단어퍼즐 2

https://www.acmicpc.net/problem/13502

  • 코드 내에 26000줄의 사전을 내장해야 하는 이상한 문제
  • 여튼 Trie는 recursion을 쓰지 않는게 안정적이다.
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
struct Node {
  bool isEnd = false;
  Node *next[26];
  Node() {
    for(int i = 0; i < 26; i++) next[i] = nullptr;
  }
};

class Trie {
  Node root;
public:
  void insert(char *s) {
    int size = strlen(s);
    Node *cur = &root;
    for (int i = 0; i < size; i++) {
      int p = s[i] - 'A';
      if(!cur->next[p])
        cur->next[p] = new Node();
      cur = cur->next[p];
    }
    cur->isEnd = true;
  }
  Node* check(char c, Node* cur=nullptr) {
    if (cur == nullptr)
      cur = &root;
    return cur->next[c - 'A'];
  }
};

class Board {
  Trie trie;
  char board[5][5];
  char visit[5][5];
  char buf[100];
  bool bound(int x, int y) {
    return x >= 0 && x < 5 && y >= 0 && y < 5;
  }
  const int dx[8] = {-1,-1,0,1,1,1,0,-1};
  const int dy[8] = {0,1,1,1,0,-1,-1,-1};
public:
  void input() {
    for (char *s : dict)
      trie.insert(s);
    for(int i = 0; i < 5; i++)
      for(int j = 0; j < 5; j++)
        cin >> board[i][j];
  }
  int solve() {
    int ans = 0;
    memset(visit, 0, sizeof(visit));
    for(int i = 0; i < 5; i++) {
      for(int j = 0; j < 5; j++) {
        visit[i][j] = 1;
        ans += go(i, j, nullptr);
        visit[i][j] = 0;
      }
    }
    return ans;
  }
  int go(int x, int y, Node* cur) {
    cur = trie.check(board[x][y], cur);
    if(!cur) return 0;
    int ans = cur->isEnd;
    cur->isEnd = 0;
    for(int i = 0; i < 8; i++) {
      const int nx = x + dx[i];
      const int ny = y + dy[i];
      if(visit[nx][ny] || !bound(nx,ny)) continue;
      visit[nx][ny] = 1;
      ans += go(nx, ny, cur);
      visit[nx][ny] = 0;
    }
    return ans;
  }
};

int main() {
  Board board;
  board.input();
  cout << board.solve();
}