글 읽기 - [c언어]틀렸습니다라고 나오는데요. 반례 좀 찾아주시면 감사하겠습니다.

jjonggx 5년 전 0

컴파일 정상적으로 되고 예제도 5개 모두 이상없이 출력되는데 자꾸 틀렸다고 나옵니다.ㅠㅠ

혹시 반례를 알수 있을까요? 게시판의 반례들도 찾아서 넣어봤는데 모두 맞았다고 나오는데.. 이상하네요.

한번 봐주시면 정말 감사하겠습니다.

#include <stdio.h>
#define N 1000
#define M 1000
#define INF 100000

int n,m;
int a[N+2][M+2]; // 처음 입력 받은 데이터 
int b[N+2][M+2]; // 날짜 업데이트 
int front=1,rear,Q[N*M*9+2];
int dy[4]={0,1,0,-1};
int dx[4]={1,0,-1,0};

void input(void)
{
	scanf("%d %d",&m,&n);
	for(int i =1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&a[i][j]);
			b[i][j]=INF; //날짜 업데이트하는 배열을 INF로 초기화 
		}
}

void bfs(int sy, int sx)
{
	front=1,rear=0;
	Q[++rear]=sy;
	Q[++rear]=sx;
	b[sy][sx]=0;
	while(front<=rear)
	{
		int y = Q[front++];
		int x = Q[front++];
		for(int i =0 ;i<4;i++)
		{
		    int ty=y+dy[i];
			int tx=x+dx[i];
			if(ty>=1&&ty<=n&&tx>=1&&tx<=m&&a[ty][tx]!=-1&&b[ty][tx]>b[y][x]+1)
			{
				Q[++rear]=ty;
				Q[++rear]=tx;
				b[ty][tx]=b[y][x]+1;//최소날짜으로 업데이트함 

			}
		}

	}
}

void process(void)
{
	for(int i =1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(a[i][j]==1)
				bfs(i,j); //익은 토마토가 있다면 bfs를 실행함. 
				
}

void output(void)
{
	int max = 0;
	int cnt = 0;

	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(a[i][j]==0&&b[i][j]==INF)
				cnt++; // 처음 입력 받은 데이터가 0인데 날짜업데이트하는 배열에서 INF로 있을 때 증가 시킴.  
				
			if(b[i][j]>max&&b[i][j]!=INF)
				max=b[i][j];
		}


	if(cnt>0)
		printf("-1\n");
	else
		printf("%d\n",max);
}

int main(void)
{
	input();
	process();
	output();
	return 0;
}

jjonggx 5년 전 0

process부분에서 토마토가 있을때마다 bfs()를 실행하는 것이 문제였습니다.

input부에서 토마토가 있는 것을 확인하고 Q[]에 바로넣은 다음 bfs()를 한번만 실행하는 것으로 바꾸니 pass가 되네요..

다른 분들에게도 도움이 되었으면 좋겠습니다.

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

문제

문제

출처

ICPC

[c언어]틀렸습니다라고 나오는데요. 반례 좀 찾아주시면 감사하겠습니다.

jjonggx 5년 전 0

jjonggx 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말