BOGGLE 문제 예외 케이스를 찾지 못하겠습니다..

  • 임정민
    임정민

    제가 재귀 공부하면서 구현해본 코드입니다.
    많이 부족하지만 2일동안 고생해서 짜고 있는 중입니다.

    시간초과가 날것은 알고 구현하고 있습니다.
    우선 재귀적으로 풀어본 후 동적계획법을 시도해보고싶은데
    시간초과도 되지 않고 바로 오답이라고 나오네요..

    제출시 오답으로만 나오고 케이스가 나오지 않아 고생하고 있습니다.

    아무래도 제가 코딩방법 자체가 문제인가 하여
    답답하네요..

    도움부탁드리겠습니다.

    #include <iostream>
    using namespace std;
    
    const int TABLESIZE = 5;
    char table[TABLESIZE+2][TABLESIZE+2];
    char str[10][12];
    
    int C, N;
    
    int xDirection[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
    int yDirection[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
    
    void ImemSet(void* buffer, int c, size_t n);
    void inputData();
    bool isPossible(int x, int y, int index, char *str);
    
    int main() {
        inputData();
    
        bool isMatched = false;
    
        for(int n = 0; n<N; n++) {
            isMatched = false;
            for(int i = 0; i<TABLESIZE; i++) {
                for(int j = 0; j<TABLESIZE; j++) {
                    if(isPossible(i, j, 0, str[n])) {
                        isMatched = true;
                        break;
                    }
                }
                if(isMatched) {
                    break;
                }
            }
            if(isMatched) {
                cout << str[n] << " YES" << endl;
            } else {
                cout << str[n] << " NO" << endl;
            }
            //getchar();
        }
    
        return 0;
    }
    
    bool isPossible(int x, int y, int index, char *str) {
        if(x<0 || y<0 || x>=TABLESIZE || y>=TABLESIZE) {
            return false;
        }
        if(table[x][y]!=str[index]) {
            return false;
        }
    
        if(str[index+1] == '\0') {
            return true;
        }
    
        for(int i = 0; i<8; i++) {
            if(isPossible(x+xDirection[i], y+yDirection[i], index+1, str) ) return true;
        }
    
        return false;
    }
    
    void inputData() {
        scanf("%d\n", &C);
    
        for(int c = 0; c<C; c++) {
            ImemSet(table, 0, sizeof(table));
            ImemSet(str, 0, sizeof(str));
    
            for(int i = 0; i<TABLESIZE; i++) {
                for(int j = 0; j<TABLESIZE; j++) {
                    cin >> table[i][j];
                }
            }
            scanf("%d\n", &N);
    
            for(int i = 0; i<N; i++) {
                scanf("%s", str[i]);
            }
            //getchar();
        }
    }
    
    void ImemSet(void* buffer, int c, size_t n) {
        char* temp = (char*) buffer;
        for(int i = 0; i<n; i++) *temp++ = (char)c;
    }
    

    8년 전
1개의 댓글이 있습니다.
  • LiSA
    LiSA

    테스트 케이스의 숫자를 예제에 있는 1만 하지 마시고 2 이상으로 넣고 돌려보세요


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