글 읽기 - C++ 1012 유기농 배추 문제의 반례가 궁금합니다.

ko8235 3년 전 0

이전 질문글들 읽으면서 나오는 반례들 다 넣어봤는데 잘나옵니다. ㅠㅠㅠ

어떤 부분에서 실수가 있었는지 한번 봐주시면 정말 감사하겠습니다...

(x, y가 제가 알던 것과 반대로 되어있어서 입력부터 반대로 받았습니다)

#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
int t,m,n,k;
int map[51][51],chk[51][51];

void bfs(int x, int y){
    queue<int> qx, qy;
    qx.push(x);
    qy.push(y);
    
    while(1){
        if(qx.empty()) break;
        if(qx.front()-1>0 && chk[qx.front()-1][qy.front()]==0 && map[qx.front()-1][qy.front()]==1){
            qx.push(qx.front()-1);
            qy.push(qy.front());
            chk[qx.front()-1][qy.front()]=1;
        }
        if(qx.front()+1<=m && chk[qx.front()+1][qy.front()]==0 && map[qx.front()+1][qy.front()]==1){
            qx.push(qx.front()+1);
            qy.push(qy.front());
            chk[qx.front()+1][qy.front()]=1;
        }
        if(y-1>0 && chk[qx.front()][qy.front()-1]==0 && map[qx.front()][qy.front()-1]==1){
            qx.push(qx.front());
            qy.push(qy.front()-1);
            chk[qx.front()][qy.front()-1]=1;
        }
        if(y+1<=n && chk[qx.front()][qy.front()+1]==0 && map[qx.front()][qy.front()+1]==1){
            qx.push(qx.front());
            qy.push(qy.front()+1);
            chk[qx.front()][qy.front()+1]=1;
        }
        qx.pop();
        qy.pop();
    }
    return;
}
int main()
{
    int res;
    scanf("%d",&t);
    
    for(int i=0;i<t;i++){
        for(int j=0;j<51;j++){
            memset(map[j],0,sizeof(int)*51);
            memset(chk[j],0,sizeof(int)*51);
        }
        res=0;
        scanf("%d %d %d",&n,&m,&k);
        for(int j=0;j<k;j++){
            int x,y;
            scanf("%d %d",&y,&x);
            map[x][y]=1;
        }
        for(int j=0;j<m;j++){
            for(int k=0;k<n;k++){
                if(map[j][k]==1 && chk[j][k]==0){
                    chk[j][k]=1;
                    bfs(j,k);
                    res++;
                }
            }
        }
        printf("%d\n",res);
    }
    return 0;
}

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

문제

문제

출처

ICPC

C++ 1012 유기농 배추 문제의 반례가 궁금합니다.

ko8235 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말