글 읽기 - 테스트케이스는 모두 맞는데 어디가 틀린지 모르겠습니다.

andrealgorithm 5년 전 0

테스트 케이스는 모두 맞고 논리도 맞는거 같은데 반례를 알 수 있을까요??

//인구이동
#include <cstdio>
#include <queue>
#include <algorithm>

using namespace std;

int N,L,R;
bool is_moved = false;
int sum =0, cnt =1, group=0;
int each_num =0;
int map[51][51] ={0};
int copy_map[51][51] ={0};
bool visited[51][51] = {0};
int dx[] ={1,-1,0,0};
int dy[] ={0,0,1,-1};

struct Pair{
    int x,y;
};

void init(){
    for(int i =0; i<N; i++){
        for(int j =0; j<N; j++){
            visited[i][j] = false;
        }
    }
}


void bfs(int a, int b){
    queue <Pair> q;
    q.push({a,b});
    int diff=0;

    while(!q.empty()){
        Pair temp = q.front();
        q.pop();
        visited[temp.x][temp.y] = true;

        for(int i =0; i<4; i++){
            int x1 = temp.x +dx[i];
            int y1 = temp.y +dy[i];

            if(x1 <0 || x1>=N || y1<0 || y1>=N)
                continue;

            if(visited[x1][y1])
                continue;

            diff = abs(map[x1][y1] - map[temp.x][temp.y]);
            
            //차이 절대값 이 인구이동 범위내에 있다. 
            if( L <= diff && diff <=R){
                copy_map[x1][y1] =1;    //이동할 좌표만 copy_map 에  표시 
                sum += map[x1][y1];  
                cnt++;
                visited[x1][y1] = true;
                q.push({x1,y1});
            }             
        }
    }
//    printf("group =%d, standatd = %d ,sum =%d, cnt =  %d, sum/cnt =%d\n",group, map[a][b],sum,cnt, sum/cnt);


    if(sum/cnt != map[a][b])   //인구이동이 있었다 
        is_moved = true;

    each_num = sum/cnt;  
    if(is_moved){    
        for(int i =0; i<N; i++){
            for(int j =0; j<N; j++){
                if(copy_map[i][j] ==1)   //이동했던 좌표를 실제 맵에다 넣기 
                     map[i][j] = each_num;
            }
        }
        //보여주기
/*         for(int i =0; i<N; i++){
            for(int j =0; j<N; j++){
                printf("%2d ",map[i][j]);
            }
            printf("\n");
        }
        printf("\n\n"); */
    }

    sum =0;
    cnt =1;
}

int main(){
    scanf("%d %d %d",&N,&L,&R);

    for(int i =0; i<N; i++){
        for(int j =0; j<N; j++){
            scanf("%d",&map[i][j]);
        }
    }
    group =0;
    int round =0;
    while(1){
        sum =0; 
        for(int i =0; i<N;i++){   //전체를 돌리는데 
            for(int j =0; j<N; j++){
                if(!visited[i][j]){ //방문안한것 중 
                    sum += map[i][j];
                    bfs(i,j);    
                    if(is_moved) group++;  //인구이동이 있었다 grouping 추가  
                    is_moved= false;
                }
            }
        }

        if(group !=0){ //이동 있었다 
            round++;   //전체 맵기준 이동횟수 
            group =0;
        }
        else{
            printf("%d\n",round);
            break ;
        }
        init();
    }

    return 0;
}

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

문제

문제

출처

ICPC

테스트케이스는 모두 맞는데 어디가 틀린지 모르겠습니다.

andrealgorithm 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말