글 읽기 - 어디가 틀린건지 모르겠습니다.

teamaae 6년 전 0

문제를 잘못 이해한건지...

제가 생각한 케이스는 전부 통과합니다. 거기에 질문 게시판에 올라온 테스트 케이스도 전부 통과합니다.

하지만 채점 돌리면 가차없이 바로 "틀렸습니다"가 나옵니다.

런타임 에러가 아니니, 메모리 문제도 아니고

시간 초과도 아닌데... 그럼 알고리즘에 문제가 있다는 것이니, 반례가 있다는 것이고 ㅠㅠ.. 그걸 못찾겠습니다.

고수 분들.. 도와주시면 정말 감사드리겠습니다.

#include <stdio.h>
#include <stdlib.h>
#include <queue>
using namespace std;
int main(void){
    int N,M;
    int zero_flag=1, minus_flag=1;
    int max=0;
    queue<int> que;
    
    scanf("%d %d", &N, &M);
    int a[1001][1001] ={0,};
    //scanf 받으면서 전부 0, -1인지 또는 전부 1, -1인지 check
    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
            scanf("%d", &a[i][j]);
            if(a[i][j]==1){
                minus_flag=0;
        	    que.push(i*N+j);
            }
            else if(a[i][j]==0)
                zero_flag=0;
        }
    }
    if(minus_flag==1){
	    printf("-1");
        return 0;
    }
    if(zero_flag==1){
    	printf("0");
        return 0;
    }
    int front;
    //상하좌우 0인지 확인, 0이면 그곳에 자신+1 을 넣고, queue에 데이터 삽입
    //queue에 들어가는 데이터는 (세로 좌표)x(가로최대)+가로 좌표 입니다.
    //queue가 empty일때까지 반복합니다.
    while(!que.empty()){
        front=que.front();
        que.pop();
        if(front/N+1 <N && a[front/N+1][front%N] ==0){
        	a[front/N+1][front%N]=a[front/N][front%N]+1;
        	que.push(front+N);
        	
        }
        if(front/N-1 >=0 && a[front/N-1][front%N] ==0){
        	a[front/N-1][front%N]=a[front/N][front%N]+1;
        	que.push(front-N);
        	
        }
        if(front%N+1 <N && a[front/N][front%N+1] ==0){
        	a[front/N][front%N+1]=a[front/N][front%N]+1;
        	que.push(front+1);
        }
        if(front%N-1 >=0 && a[front/N][front%N-1] ==0){
        	a[front/N][front%N-1]=a[front/N][front%N]+1;
        	que.push(front-1);
        }
    }
    
    for(int i=0;i<M;i++){
    	for(int j=0;j<N;j++){
            //만약 0이 존재한다면, 안익은게 있으니 -1!
            //숫자들 중 max 값 구하기
            
            if(a[i][j]==0){
                printf("-1");
                return 0;
            }
    		if(a[i][j]>max)
    		max=a[i][j];
    	}
    }
    //0일째가 1이므로, max-1이 답
    printf("%d",max-1);

    return 0;
}

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

문제

문제

출처

ICPC

어디가 틀린건지 모르겠습니다.

teamaae 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말