BOGGLE 왜 안되는지 모르겠네요

  • gnurails
    gnurails

    BOGGLE
    아무리 해도 이상하게 나와서 질문드려요.

    #include<stdio.h>
    #include<string.h>
    int len; char data[8][8];
    int min(int x, int y)
    {
        return x<y?x:y;
    }
    int max(int x, int y)
    {
        return x>y?x:y;
    }
    bool find(char *question, int level, int x, int y)
    {
        if (level==len) return true;
        if (level==0) {
            for (int i=0; i<5; i++)
                for (int j=0; j<5; j++)
                    if (data[i][j]==question[0]) return find(question, 1, i, j);
        }
        else {
            for (int i=max(0,x-1); i<=min(4,x+1); i++)
                for (int j=max(0,y-1); j<=min(4,y+1); j++)
                    if (data[i][j]==question[level]&&(i!=x||j!=y)) return find(question, level+1, i, j);
        }
        return false;
    }
    int main()
    {
        int testCase; scanf("%d", &testCase);
        while(testCase--)
        {
            for (int i=0; i<5; i++) scanf("%s", data[i]);
            int num; scanf("%d", &num);
            char question[15];
            for (int i=0; i<num; i++) {
                scanf("%s", question);
                len=strlen(question);
                if (find(question, 0, 0, 0)) printf("%s YES\n", question);
                else printf("%s NO\n", question);
            }
        }
        return 0;
    }
    

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

    완전탐색을 하시고 있는데, 문제에도 쓰여있듯 완전탐색으로는 해결할 수 없는 문제입니다.
    작성하신 풀이에서 하나의 question에 대해 level, x, y가 모두 같으면 항상 답이 일정하다는 것을 이용해 개선할 수 있습니다.


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