boggle 게임 질문입니다

  • vicent
    vicent

    알고리즘 문제해결전략 책을 보면서 알고리즘을 공부하고 있습니다.
    첫문제로 이 보글 문제를 푸는데 도저히 잘 되지 않습니다. ㅜㅜ
    문제 밑에 있는 테스트 케이스들은 전부 제대로 통과하는데 계속 오답이 납니다.ㅜㅜ
    다른 정답들을 보면서 비교해도 제가 틀린 것 같지는 않은데 무엇이 문제인지를 모르겠어요 ㅜ
    chk배열을 통해 한 번 들어간 부분에 다시 들어가지 않도록 처리했고, 8가지 방향을 돌면서 재귀적으로 문제를 해결하도록 하였습니다.
    무엇이 문제인지 알려주시면 감사하겠습니다 ㅜㅜ

    #include <cstdio>
    #include <string.h>
    int T;
    char map[15][15];
    char word[20];
    int chk[15][15][15];
    int dirow[] = { -1, -1, -1, 0, 1, 1, 1, 0 };
    int dicol[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
    int flag;
    int cnt;
    inline int strlen(char *p)
    {
        int cnt = 0;
        while (p[cnt++]);
        return cnt-1;
    }
    int DFS(int n, int row, int col)
    {
        if (n >= cnt - 1) return 1;
        chk[n][row][col] = 1;
        if (word[n] != map[row][col]) return 0;
        for (register int i = 0; i < 8; i++)
        {
            int ni = row + dirow[i]; int nj = col + dicol[i];
            if (ni < 0 || ni > 4 || nj < 0 || nj > 4) continue;
            if (chk[n+1][ni][nj]) continue;
            if (DFS(n + 1, ni, nj) == 1) return 1;
        }
        return 0;
    }
    
    
    int main(void)
    {
        register int i, j;
        int row, col;
        int n;
        scanf("%d", &T);
        while (T--)
        {
            memset(map, 0, sizeof(map));
            for (i = 0; i < 5; i++) scanf("%s", map[i]);
            scanf("%d", &n);
            for (i = 0; i < n; i++)
            {
                flag = 0;
                cnt = 0;
                memset(chk, 0, sizeof(chk));
                scanf("%s", word);
                cnt = strlen(word);
                printf("%s ", word);
                for (row = 0; row < 5; row++)
                {
                    for (col = 0; map[row][col]; col++)
                    {
                        if (DFS(0, row, col) == 1)
                        {
                            flag = 1;
                            break;
                        }
                    }
                    if (flag) break;
                }
                if(flag) puts("YES");
                else puts("NO");
            }
        }
        return 0;
    }
    

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