BOGGLE 오답처리 문의입니다.

  • JinwooP
    JinwooP

    BOGGLE
    알고리즘 해결전략문제

    답변보고 output부분 수정하니
    속도가 대폭 빨라졋어요. 그부분을 놓쳣엇네요
    문자열과 모든 변수부분 초기화에 신경썻는데
    오답처리가 나서 제가 간과한부분이 어디있는지
    조언좀 부탁드립니다.

    꼭 책의 모든 문제를 풀면서 실력을 쌓고싶습니다!!

    #include<stdio.h>
    #include<string.h>
    #include<memory.h>
    
    
    
    char word[11];   
    char back_g[6][6]; 
    int cache[11][6][6];  // -1 안들림, 0 들렸지만 인접에 없음
    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;
    
    
                }
            }
    
        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;  // TESTCASE 
    
        int matching_word = 0;
        scanf("%d", &C);
    
        while (C-- > 0)
        {   
            i = 0;
            memset(back_g, 0, sizeof(back_g));
    
            while (i < 5)
            {
                scanf("%s", back_g[i]);
                i++;
            }
    
            scanf("%d", &N);
    
            for (i = 0; i < N; i++) {
    
                memset(cache, -1, sizeof(cache));
                memset(word, 0, sizeof(word));
                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;
    }
    

    8년 전
0개의 댓글이 있습니다.
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.