DIAMOND 문제 오답이 뜨네요 ㅜㅜ 테스트케이스 구합니다. ㅋㅋ

  • ginger
    ginger

    제가 구현한 알고리즘은 정말 간단합니다!

    idx, jdx부터 max_depth까지 정말 나이브하게 다이아몬드 탐색을 해서 최대 길이를 잽니다.

    시간도 여유있게 들어가구요... 근데 오답이 자꾸 뜨네요 ㅋㅋ

    테스트 케이스 외에도 다음과 같은 테스트도 해봤는데 잘 되서... 난감합니다. ㅠㅠ
    (사실 몇가지로 더 실험해봤는데 잘 되더군요..)

    6
    3
    ...
    ...
    ...
    4
    #..#
    #..#
    #..#
    .##.
    4
    ....
    .##.
    ####
    .##.
    4
    #.#.
    .#.#
    .##.
    #..#
    3
    ..#.
    .###
    ..#.
    5
    #####
    #####
    #####
    #####
    #####

    도움이 필요합니다. 고수님들!
    빠트린 부분이 어느 부분일까요?!

    #include <iostream>
    
    using namespace std;
    
    static int N=0;
    static int M= -1;
    static int word_map[50][50] = {0, };
    static int max_length = 0;
    
    int FindDiamond(int idx, int jdx, int max_depth){
        //idx, jdx부터 아래로 만들어지는 다이아몬드를 찾으면 최대 길이를, 못찾으면 -1을 반환한다.
    
        if(word_map[idx][jdx] == 0)
            return -1;
    
        int depth = 1;
        int mid = 0;
        if(max_depth % 2 == 0)
            mid = max_depth/2;
        else
            mid = max_depth/2 + 1;
        int begin = -1, end = 1;
    
        int flag = 1;
        while(depth < mid && flag == 1){
            for(int i=(jdx+begin); i<=(jdx+end); i++){
                if(word_map[depth][i] == 0){
                    flag = 0;
                    break;
                }
            }
            depth++;
            begin--;
            end++;
        }
        if(flag == 0)
            return -1;
        begin++;
        end--;
        while(depth >= mid && begin < end && flag == 1){
            for(int i=(jdx+begin); i<=(jdx+end); i++){
                if(word_map[depth][i] == 0){
                    flag = 0;
                    break;
                }
            }
            depth++;
            begin++;
            end--;
        }
        return depth;               //depth만큼이 다이아몬드의 최대길이가 되지.
    }
    
    
    int main(void){
        int C=0;
        cin>>C;
        while(C-->0){
            max_length = 0;
            cin>>N;
            getchar();
            int row_cnt=0;
            int word_cnt = 0;
            while(row_cnt < N){
                char ch = getchar();
                if(ch == 10){
                    word_cnt = 0;
                    row_cnt++;
                    continue;
                }
                if(ch == '#')
                    word_map[row_cnt][word_cnt] = 1;
                word_cnt++;
                if(word_cnt > M)
                    M = word_cnt;
            }
    
            for(int i=0; i<N; i++){
    
                for(int j=0; j<M; j++){
    
                    for(int k=N-i; k>0; k--){
                        int length = FindDiamond(i, j, k);
                        if(length > max_length)
                            max_length = length;
                    }
                }
    
            }
    
    
            cout<<max_length<<endl;
        }
        return 0;
    }
    

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

    코드를 자세히 보지는 않았는데 초기화가 제대로 되는지 확인해 보시기 바랍니다.


    10년 전 link
  • ginger
    ginger

    초기화 루틴을 추가시켜도 오답이네요 ㅋㅋ ㅠㅠㅜ 감사합니다. 계속 보고 있습니담. ㅎㅎ


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