[[problem:BOGGLE]]
[[알고리즘 문제해결전략|problem:BOGGLE]]

cache 배열을 이용하여 재귀탐색중 인접행렬에서
찾을수있는 다음문자가 없다면 탐색할 필요 없도록 하였습니다.
초기화 부분도 신경썻는데 어느부분에서 문제가 발생하였는지 조언 부탁드립니다.

#include<stdio.h>
#include<string.h>
#include<memory.h>

char word[11];   
char back_g[6][6]; 
int cache[11][6][6];
int neighbor_dy[8] = {-1,-1,0,1,1,1,0 ,-1 };
int neighbor_dx[8] = { 0,1,1,1,0,-1,-1,-1 };
int w_lenght = 0;  
int output = 0;    

int check_word(int y, int x, int word_index)
{
    
    int dx, dy = 0;

    if (word_index == w_lenght)
        return 1;

    if (cache[word_index][y][x] == 0)
        return 0;

    if(cache[word_index][y][x] == -1)

    for(int i=0;i<8;i++)
    {       
            dx = x + neighbor_dx[i];    
            dy = y + neighbor_dy[i];

            if ( dx < 0 || dx > 4 || dy < 0 || dy > 4 )
                continue;

            if (back_g[dy][dx] == word[word_index])
            {
                cache[word_index][dy][dx] = 1;
                output = check_word(dy,  dx , word_index + 1);
            }
        }
    if (output == 1)
        return 1;
    else {
        cache[word_index][y][x] = 0;
        return 0;
    }
}



int search()
{
    output = 0;
    int ans = 0;

    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
        {
            if (back_g[i][j] == word[0])
                ans = check_word(i, j, 1);

            if (ans == 1)
                return 1;
        }

    return 0;

}


int main()
{
    
    int N = 0;    // word 개수
    int i = 0;
    int C = 0;

    int matching_word = 0;
    scanf("%d", &C);
    
    while (C-- > 0)
    {   
        i = 0;

        while (i < 5)
        {
            scanf("%s", back_g[i]);
            i++;
        }

        scanf("%d", &N);

        for (i = 0; i < N; i++) {

            memset(cache, -1, sizeof(cache));
            matching_word = 0;
            w_lenght = 0;
            scanf("%s", word);
            w_lenght = strlen(word);
        
            matching_word = search();

            if (matching_word == 1)
                printf("%s YES\n", word);
            else
                printf("%s NO\n", word);

        }
    }

    return 0;
}