글 읽기 - 이 코드에서 반례를 알려주세요!! 예제는 다 맞았어요ㅠㅠ

alex1221 4년 전 0

문제에 나와있는 예제는 다 맞는데 왜 틀렸는지

반례를 알려주시면 감사하겠습니ㅇ다!!

#include <bits/stdc++.h>

using namespace std;

int tomato[1003][1003]={ };
int N,M;
int posqu[3][1003]={ };
int fin=-1, flag=0, multi=1,coun=0, temp=0;
int tempcoun=0;

void addd(int a, int b);
void change(void);

int main()
{
    cin>>M>>N;

    for(int x=1;x<=N;x++)
    {
        for(int y=1;y<=M;y++)
        {
            cin>>tomato[x][y];
            multi*=tomato[x][y];



            if(tomato[x][y]==1)
            {
                fin+=1;
                posqu[1][fin]=x;
                posqu[2][fin]=y;
            }
        }
    }

    if(multi != 0)
        cout<<0;
    else
    {
        change();

        for(int k=1; k<=N; k++)
        {
            for(int o=1; o<=M; o++)
            {
               if(tomato[k][o]==0)
               {
                   cout<<-1;
                   return 0;
               }
            }


        }


cout<<coun;
    }
    return 0;
}

void addd(int a, int b)
{
    fin+=1;
    posqu[1][fin]=a;
    posqu[2][fin]=b;

}

void change(void)
{
    while(temp<=fin)
    {
        tempcoun=1;
        if(tomato[posqu[1][temp]-1][posqu[2][temp]] == 0&& posqu[1][temp]-1 >=1 && posqu[1][temp]-1<= N && posqu[2][temp]>=1 && posqu[2][temp]<=M )
        {
            tomato[posqu[1][temp]-1][posqu[2][temp]]=1;
            tempcoun=0;
            addd(posqu[1][temp]-1, posqu[2][temp]);
        }

        if(tomato[posqu[1][temp]][posqu[2][temp]+1] == 0 && posqu[1][temp]>=1 && posqu[1][temp]<= N && posqu[2][temp]+1>=1 && posqu[2][temp]+1<=M )
        {
            tomato[posqu[1][temp]][posqu[2][temp]+1]=1;
            tempcoun=0;
            addd(posqu[1][temp], posqu[2][temp]+1);
        }

        if(tomato[posqu[1][temp]+1][posqu[2][temp]] == 0 && posqu[1][temp]+1 >=1 && posqu[1][temp]+1<= N && posqu[2][temp]>=1 && posqu[2][temp]<=M )
        {
            tomato[posqu[1][temp]+1][posqu[2][temp]]=1;
            tempcoun=0;
            addd(posqu[1][temp]+1,posqu[2][temp]);
        }

        if(tomato[posqu[1][temp]][posqu[2][temp]-1] == 0 && posqu[1][temp] >=1 && posqu[1][temp]<= N && posqu[2][temp]-1>=1 && posqu[2][temp]-1 <=M)
        {
            tomato[posqu[1][temp]][posqu[2][temp]-1]=1;
            tempcoun=0;
            addd(posqu[1][temp], posqu[2][temp]-1);
        }
        //cout<<temp<<endl;

        temp+=1;
        if(flag<temp && temp<=fin)
        {
            coun+=1;
            flag=fin;
        }
    }
}

nahwasa 4년 전 0

반례입니다.

alex1221 4년 전 1

30분동안 생각을 해봤는데 제 코드의 문제점이 무엇인지는 알겠는데 어느 부분을 어떻게 고쳐야할지를 잘 모르겠습니다

제 코드에서 처음 1을 posqu라는 배열에 입력받는데 반례로 알려주신 0행 0열의 1 처럼 주위에 0이 없는 경우에는 카운트가 제대로 되지 않는것 같습니다

이런경우에는 코드를 어떻게 고쳐야할까요??

nahwasa 4년 전 0

음.. 코드 스타일이 저랑 많이 다르셔서 이해하기가 다소 힘들긴한데요,

이런 경우엔 한스탭씩 출력문을 추가하시던지 디버깅 모드를 사용하셔서

진행이 어떻게 되는지 차근차근 한번 보시는걸 추천드립니다. (일단 매번 posqu배열 전체가 어떻게 변화되는지 보시는게 좋겠네요.)

일단 말씀하신 부분에 대해서는(주위에 0이 없는경우) 애초에 카운트 할 필요가 없으니 아무처리도 않고 다음 temp로 넘어가시도록 하면 되겠지요.

사실 BFS쪽으론 기본적인 문제라 BFS 관련 문제 푸시기 위해 BFS쪽 좀더 찾아보며 공부하시는걸 추천드립니다!

이런 문제 엄청많더라구요.

일단 졸려서.. 낼도 잘 해결 안되시면 댓글 달아주시면 제대로 보고 다시 답변하겠슴다.

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

문제

문제

출처

ICPC

이 코드에서 반례를 알려주세요!! 예제는 다 맞았어요ㅠㅠ

alex1221 4년 전 0

nahwasa 4년 전 0

alex1221 4년 전 1

nahwasa 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말