BOGGLE문제 질문합니다

  • wowrupi
    wowrupi

    안녕하세요, 책을보면서 공부하고있는데요 6장에서 보고 완전탐색으로만 코드를 짜놓고 8장공부한뒤에 메모제이션 기법을 적용시켰습니다

    저같은 경우는 캐시를 cache[5][5][8]; 이렇게 두고
    해당좌표에서 8방향 탐색을해서 재귀함수를 호출을 했을때 답을 못찾는다면 재귀함수가 종료하면서 cache에 값을저장을 하여 오답인 경로를 재탐색하게 하지 못하게하였는데, 테스트 케이스도 다맞고
    댓글에 제시해주신 최악의 테스트케이스도 잘맞는거, 같은데 오답이나오네요.

    문제를 정답을 맞지 않으면 다른문제로 잘못넘어가는 성격이라 죽겠습니다.여러가지 케이스를 만들어서 넣어봐도 문제점을 못찾겠네요

    #탐색하는 재귀함수 코드 첨부합니다.

    2차원배열에서 탐색하는 첫번째 문자가 일치하면 해당 재귀함수를 MAIN에서 호출 합니다.
    bool Find(char* p, int x, int y)
    {

    if (x > 5 || y > 5)
        return false;
    //기저사례
    if (p[0] == '\0')
        return true;
    
    for (int i = 0; i<8; i++)
    {
        if (p[0] == str[x + way[i][0]][y + way[i][1]])
        {
            if (cache[x][y][i] == -1 )
            {
                if (Find(p + 1, x + way[i][0], y + way[i][1]))
                    return true;                        
                cache[x][y][i] = 0;
    
            }
        }
    }
    
    return false;

    }

    감사합니다


    9년 전
2개의 댓글이 있습니다.
  • 샥후
    샥후

    1
    ABCXX
    BEXXX
    CDXIH
    XXXJG
    XXHGF
    2
    ABCDEBC
    FGHIJGH


    9년 전 link
  • wowrupi
    wowrupi

    2개다 YES가 나와야지 맞는거죠?


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