2819. 격자판의 숫자 이어 붙이기 26 Nov 2019 in Algorithm on SWEA 문제링크[풀이]#include <iostream> #define MAXN 5 #define ISVALID(r, c) (r <= 4 && r >= 1 && c <= 4 && c >= 1) using namespace std; int T, N, sol; char MAP[MAXN][MAXN]; int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; typedef struct Trie { bool isleaf; Trie * child[10]; }; Trie nodes[50000]; int nmtop; Trie * _malloc() { nodes[nmtop].isleaf = false; for (int i = 0; i < 10; ++i) nodes[nmtop].child[i] = 0; return &nodes[nmtop++]; } Trie root; void insert(Trie * parent, char * str) { if (*str == '\0') { if (parent->isleaf == false) { sol++; parent->isleaf = true; } else if (parent->isleaf == true) return; } else { if (parent->child[*str - '0'] == '\0') parent->child[*str - '0'] = _malloc(); insert(parent->child[*str - '0'], str + 1); return; } } void dfs(int depth, char *str, int row, int col) { str[depth] = MAP[row][col]; if (depth == 6) { str[7] = '\0'; insert(&root, str); } else { int newrow, newcol; for (int i = 0; i < 4; i++) { newrow = row + dir[i][0]; newcol = col + dir[i][1]; if (ISVALID(newrow, newcol)) { dfs(depth + 1, str, newrow, newcol); } } } } void solve() { for (int i = 1; i < MAXN; i++) { for (int j = 1; j < MAXN; j++) { char str[10]; dfs(0, str, i, j); } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> T; for (int i = 1; i <= T; ++i) { sol = 0; nmtop = 0; root.isleaf = false; for (int i = 0; i < 10; i++) root.child[i] = '\0'; for (int j = 1; j <= 4; ++j) { for (int k = 1; k <= 4; ++k) { cin >> MAP[j][k]; } } solve(); cout << "#" << i << " " << sol << "\n"; } }