글 읽기 - 9202 "Boogle" 도움 요청드립니다.

ashtar 5년 전 0

제가 빠뜨린 부분을 도저히 찾을 수가 없네요 ㅠ,ㅠ

혹시 샘플 데이터나 예외케이스 알려주시면 큰 도움 될 것 같습니다!

간략히 아래와 같이 코드작성 하였습니다.

trie 로 데이터 저장
4x4 그리드를 모두 backtracking 수행하여 단어 검색
검색한 단어 unordered_map 에서 검색하여 중복처리함

#include 
#include 
#include

using namespace std;

#define MAX 4
#define WORD_MAX 300000
#define MAX_LENGTH 8 + 1

int N, M;
char map[MAX][MAX];
bool visited[MAX][MAX];
char words[WORD_MAX][MAX_LENGTH];
bool word_checker[WORD_MAX];
unordered_map word_map;

string answer;
int score, max_length , num_words;

int dx[8] = { -1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = { -1, 0, 1, -1, 1, -1, 0, 1};

struct Trie {
bool end;
Trie *next[26];

Trie() : end(false) { for (int i = 0; i < 26; i++) next[i] = NULL; }
~Trie() { for (int i = 0; i < 26; i++) if (next[i]) delete next[i]; }
void add(const char *c) {
if (*c == 0) {
end = true;
} else {
int index = *c - 'A';
if (!next[index])
next[index] = new Trie;
next[index]->add(c + 1);
}
}
};

void backtracking(int r, int c, Trie *current, int length, char ch[MAX_LENGTH]) {
int index = map[r][c] - 'A';

if (current->end) {
int index = -1;

ch[length] = 0;
if (max_length < length
|| (max_length == length && answer > ch)) {
max_length = length;
answer = ch;
}

unordered_map::iterator it = word_map.find(ch);

if (index != -1 && word_checker[index] == false) {
word_checker[index] = true;
num_words++;

switch (length) {
case 3:
case 4:
score += 1; break; 
case 5:
score += 2; break;
case 6:
score += 3; break;
case 7:
score += 5; break;
case 8:
score += 11; break;
}
}
}

visited[r][c] = true;
if (current->next[index]) {
for (int i = 0; i < 8; i++) {
if (r + dx[i] >= 0 && r + dx[i] < MAX
&& c + dy[i] >= 0 && c + dy[i] < MAX 
&& visited[r + dx[i]][c + dy[i]] == false) {
ch[length] = map[r][c];
backtracking(r + dx[i], c + dy[i], current->next[index], length + 1, ch);
}
}
}
visited[r][c] = false;
}

void init_visited() {
for (int i = 0; i < MAX; i++)
for (int j = 0; j < MAX; j++)
visited[i][j] = false;
}

int main() {
Trie *root = new Trie();

cin >> N;

for (int i = 0; i < N; i++) {
cin >> words[i];
root->add(words[i]);
word_map.insert(make_pair(words[i], i));
}

cin >> M;

for (int testCase = 0; testCase < M; testCase++) {
max_length = score = num_words = 0;
for (int i = 0; i < N; i++)
word_checker[i] = false;

for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
cin >> map[i][j];
}
}

for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
char ch[MAX_LENGTH];

init_visited(); 
backtracking(i, j, root, 0, ch);
}
}
cout << score << " " << answer << " " << num_words << endl;
}
return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

9202 "Boogle" 도움 요청드립니다.

ashtar 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말