BOGGLE 문제 가지치기

  • cjdahrl
    cjdahrl

    아래는 코드입니다.

    #include <iostream>
    #include <string>
    #include <vector>
    
    using namespace std;
    
    char chrArray[5][5];
    
    int xAdjustment[8] = { -1, -1, -1, 0, 1, 1, 1, 0 };
    int yAdjustment[8] = { -1, 0, 1, 1, 1, 0, -1, -1 };
    
    bool hasWord(int x, int y, string word);
    
    int main(){
    
        int nTestCase;
        int nFindCount;
        string strFindWord;
        bool bExist;
        bool flag;
    
        cin >> nTestCase;
    
        // input foundation
        for(int i = 0; i < 5; i++)
        for(int j = 0; j < 5; j++)
            cin >> chrArray[i][j];
    
        cin >> nFindCount;
    
        for(int h = 0; h < nFindCount; h++) {
            cin >> strFindWord;
    
            bExist = false;
            flag = false;
    
            for(int i = 0; i < 5; i++) {
                for(int j = 0; j < 5; j++)
                {
                    if(hasWord(i, j, strFindWord)) {
                        bExist = true;
                        flag = true;
                    }
                    if(flag) break;
                }
                if(flag) break;
            }
            if(bExist) cout << strFindWord << " YES" << endl;
            else cout << strFindWord << " NO" << endl;
        }
    } // main()
    
    bool hasWord(int x, int y, string word) {
        pair<int, int> direction;
        vector< pair<int, int> > existDirection;
    
        if (x > 5 || x < 0 || y > 5 || y < 0)   return false; // 범위 초과
        if (chrArray[x][y] != word[0])          return false; // 첫글자 다름
        if (word.size() == 1)                   return true;  // 단어가 한글자일 때
    
        // 범위내, 첫글자가 같고, 글자수가 하나가 아닐때
        for (int i = 0; i < 8; i++) {
            // 다음 글자가 존재하는 방향을 저장
            if (chrArray[x + xAdjustment[i]][y + yAdjustment[i]] == word[1]) {
                direction.first = xAdjustment[i];
                direction.second = yAdjustment[i];
                existDirection.push_back(direction);
            }
        }
        // 다음글자가 존재하는 방향만 검사
        if (existDirection.size()) {
            for (vector< pair<int, int> >::iterator itr = existDirection.begin(); itr != existDirection.end(); itr++) {
                if (hasWord(x + (*itr).first, y + (*itr).second, word.substr(1))) return true;
            }
        }
        return false;
    } // hasWord()
    

    보글문제 8장 내용 참고하면서 가지쳐내고 있는데
    어느부분을 어떻게 쳐낼지 모르겠습니다.
    도움 주시면 감사하겠습니다.


    10년 전
1개의 댓글이 있습니다.
  • Being
    Being

    예를 들어,

    AAAAA
    AAAAA
    AAAAA
    AAAAA
    AAAAA

    같은 입력에서 AAAAAAAAAB같은 단어를 찾는다고 하면, 충분히 빠를까요?


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