글 읽기 - 반례가 있는건지 아니면 뭐가틀린건지 잘모르겠습니다.

sam6979 4년 전 0

여러가지 테스트 케이스를 넣어서 결과값을 비교했지만 맞아떨어 지는데, 틀렸다고만 뜨네요..

반례가 있는건지 아니면 뭐가 잘못된것인지 잘 모르겠습니다....

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int vertical,horizontal,i,j,k,n,cnt,lim=0;
int x,y,copx,copi,skatch[100][100]={0},bf[2][100000],ans[100000];

void bfs(int v){//BFS탐색
    if(skatch[bf[0][v]+1][bf[1][v]]==0 && bf[0][v]+1<vertical){skatch[bf[0][v]+1][bf[1][v]]=2; bf[0][lim]=bf[0][v]+1; bf[1][lim]=bf[1][v]; lim++; cnt++;}
    if(skatch[bf[0][v]-1][bf[1][v]]==0 && bf[0][v]-1>=0){skatch[bf[0][v]-1][bf[1][v]]=2; bf[0][lim]=bf[0][v]-1; bf[1][lim]=bf[1][v]; lim++; cnt++;}
    if(skatch[bf[0][v]][bf[1][v]+1]==0 && bf[1][v]+1<horizontal){skatch[bf[0][v]][bf[1][v]+1]=2; bf[0][lim]=bf[0][v]; bf[1][lim]=bf[1][v]+1; lim++; cnt++;}
    if(skatch[bf[0][v]][bf[1][v]-1]==0 && bf[1][v]-1>=0){skatch[bf[0][v]][bf[1][v]-1]=2; bf[0][lim]=bf[0][v]; bf[1][lim]=bf[1][v]-1; lim++; cnt++;}
    if(v==lim){return;}
    bfs(v+1);
}

int main(){
    scanf("%d %d %d",&vertical,&horizontal,&n);
    for(i=0;i<n;i++){
        scanf("%d %d %d %d",&x,&y,&copx,&copi);
        for(j=y;j<copi;j++){
            for(k=x;k<copx;k++){
                skatch[j][k]=1;
            }
        }
    }//sktach 2차원배열에 주어지는 케이스를 영역으로 바꾸어 복붙
    for(i=0,k=0;i<vertical;i++){
        for(j=0;j<horizontal;j++){
            if(skatch[i][j]==0){
                cnt=1;
                lim=1;
                skatch[i][j]=2;
                bf[0][0]=i;
                bf[1][0]=j;
                bfs(0);
                ans[k]=cnt;
                k++;
            }
        }
    }//영역찾기
    sort(ans,ans+k);
    printf("%d\n",k);
    for(i=0;i<k;i++){printf("%d ",ans[i]);}
}

sam6979 4년 전 1

문제는 bfs함수에서 칸이 한칸인 경우에 좌표를 넣어두는 배열안에서 초기화가 되지않고 넘어간다는데에 있었습니다 위의 bfs함수에서 4개의 if문에 끝에 && v<lim 을 추가시키니 정답이 나오는군요

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

문제

문제

출처

ICPC

반례가 있는건지 아니면 뭐가틀린건지 잘모르겠습니다.

sam6979 4년 전 0

sam6979 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말