글 읽기 - 반례가 궁금합니다 ㅜㅜ

louisdebroglie 4년 전 0

많이 풀지 않는 문제인것 같아서 반례를 찾아보려해도 잘 못 찾겠습니다 ㅜㅜ

문제를 푼 방법 자체는 9466_텀 프로젝트와 비슷한데,

check배열에 특정한 칸을 탐색 cycle에서 몇번째로 방문했는지 기록하고,

which_search배열에는 몇번째 탐색 cycle에서 특정 칸의 탐색을 했는지를 기록합니다.

(main함수에서 모든 칸에 대해 dfs를 돌리면, (1,1)칸이 1번째 탐색 cycle, (1,2)가 2번째 탐색 cycle이고, 1번째 탐색 cycle에서 check[1][1]은 1번째로 방문한 수 이므로 1인 방식입니다.)

문제는 문제에 계시된 5개의 테스트케이스는 모두 필요한 정답이 나오는데, 제출을 하면 5%정도에서 틀렸습니다로 처리되는 것입니다.

도움을 간절히 기다리고 있겠습니다.

#include <iostream>

using namespace std;

char matrix[51][51];

int check[51][51];
int which_search[51][51];

int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};

bool dfs(int curr,int curc,int which,int cnt,int& rownum,int& colnum){
    check[curr][curc]=cnt;
    which_search[curr][curc]=which;

    for(int k=0;k<4;k++){
        int nextr=curr+dx[k];
        int nextc=curc+dy[k];
        if(1<=nextr&&nextr<=rownum&&1<=nextc&&nextc<=colnum){
            if(matrix[nextr][nextc]==matrix[curr][curc]){
                if(which_search[nextr][nextc]!=which_search[curr][curc]){
                    return dfs(nextr,nextc,which,cnt+1,rownum,colnum);
                }
                else{
                    if(check[nextr][nextc]+3<=check[curr][curc]){
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int rownum,colnum;
    cin >> rownum >> colnum;

    for(int r=1;r<=rownum;r++){
        for(int c=1;c<=colnum;c++){
            cin >> matrix[r][c];
        }
    }

    int sc=1;
    for(int r=1;r<=rownum;r++){
        for(int c=1;c<=colnum;c++){
            bool flg = dfs(r,c,sc,1,rownum,colnum);
            if(flg==true){
                cout << "Yes" << '\n';
                return 0;
            }
            else{
                sc++;
                for(int k=1;k<=rownum;k++){
                    for(int t=1;t<=colnum;t++){
                        check[k][t]=0;
                    }
                }
            }
        }
    }

    cout << "No" << '\n';
    
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례가 궁금합니다 ㅜㅜ

louisdebroglie 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말