글 읽기 - 게시판 대부분의 반례를 통과했는데 반례나 틀린부분 지적부탁드립니다!!!

devbelly 4년 전 0

안뇽하세요 ㅎㅎ 새해복많이받으세요

#include <stdio.h>
#include <string.h>


int box[1000 + 2][1000 + 2];
int memo[2][1500000];
int visited[1000 + 2][1000 + 2];

int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0 ,0 ,1,-1 };
int idx,front;
int distance[1000][1000];
int M, N;
int cnt;
int num;


void paint(int w)
{
	for (int i = 1;i <= N;i++)
		for (int j = 1;j <= M;j++)
			if (box[i][j] == w) // 처음토마토를 찾았다면
			{
				distance[i][j] = 0; // 처음토마토와 처음토마토의 거리는 0
				visited[i][j] = 1; // 방문배열에 방문의 의미로 1
				memo[0][idx] = i; // 처음토마토의 col 값을 memo에 적어놓자. (queue의rear에 해당하는게 idx)
				memo[1][idx] = j; // 처음토마토의 row 값을 memo에 적어놓자. 
				idx++; //memo라는 이름의 queue의 rear인 idx 증가
			}

	while (front < idx) // 큐가 빌떄까지
	{
		int a = memo[0][front]; // col값 pop
		int b = memo[1][front]; // row값 pop
		front++; // queue의 front 증가

		for (int k = 0;k < 4;k++) // 해당 위치의 주변값 탐색하기 위한 k
		{
			if (box[a + dy[k]][b + dx[k]] == 0 && visited[a + dy[k]][b + dx[k]] == -1) // pop한 a,b의 주변에 안익은 토마토( ==0)가 있으며
																					// 그 주변에 방문하지 않았다면
			{
				box[a + dy[k]][b + dx[k]] = 1; // 해당자리에 이전거리 + 1을 새겨놓자
				memo[0][idx] = a + dy[k]; // col값을 queue에 넣기
				memo[1][idx] = b + dx[k]; // row 값을 queue에 넣기
				idx++; // queue rear 증가
				distance[a + dy[k]][b + dx[k]] = distance[a][b] + 1; // distance증가! 당연히 이전값 + 1
				visited[a + dy[k]][b + dx[k]] = 1; // 해당자리 방문표시를 위한 1
			}
		}
	}
}

int main()
{
	memset(box, -1, sizeof(box));
	memset(visited, -1, sizeof(visited));
	memset(distance, -1, sizeof(distance));
	scanf("%d%d", &M, &N);

	for (int i = 1;i <= N;i++) // 박스 입력받기
		for (int j = 1;j <= M;j++)
			scanf("%2d", &box[i][j]);

	paint(1); // 위의 설명으로 고고씽~!

	//for (int i = 1;i <= N;i++)
	//{
	//	for (int j = 1;j <= M;j++)
	//		printf("%d", box[i][j]);
	//	printf("\n");
	//}

	//for (int i = 1;i <= N;i++)
	//{
	//	for (int j = 1;j <= M;j++)
	//		printf("%d", distance[i][j]);
	//	printf("\n");
	//}

	for (int i = 1;i <= N;i++) 
		for (int j = 1;j <= M;j++)
			if (box[i][j] == 0) //박스에 안익은 토마토가 있다면
			{
				printf("-1"); // 답 -1 출력
				return 0;
			}
	// 모든 토마토가 익었다면 최댓값을 찾자

	int max = -1;
	for (int i = 1;i <= N;i++)
		for (int j = 1;j <= M;j++)
			if (distance[i][j] > max) // 만약 해당 배열값이 max 보다 크다면 
				max = distance[i][j]; // 너가 가장 큰값
	printf("%d", max); // 걸리는 일수가 된다



	return 0;
}

djm03178 4년 전 1

왜 다른 배열들은 여유분을 뒀는데 distance 배열은 딱 1000*1000인가요?

devbelly 4년 전 0

@djm03178

너무 감사드립니다...

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

문제

문제

출처

ICPC

게시판 대부분의 반례를 통과했는데 반례나 틀린부분 지적부탁드립니다!!!

devbelly 4년 전 0

djm03178 4년 전 1

devbelly 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말