글 읽기 - 톰마토마토마톰톰톰톰마톰토토토토마토토마토토토토마톰마토마토마톰톰톰톰마톰토마토

hs9200 3년 전 0

c언어 왕초보입니다...(c린이)

토마토를 풀고 있는데 저번에는 시간초과가 났습니다...

이번에는 아예 틀렸데요

저는 여기서 bfs를 한 번만 돌리라는 뜻을 왠지 잘못이해한 것 같은데

도와주세요...

#include <stdio.h>
#include <algorithm>
#include <queue>
#define M 1000
#define R 10000000
#define INF 599999999
using namespace std;
queue <int> q;
pair <int, int> yx[R + 1];
int a[M + 1][M + 1];
int d[M + 1][M + 1];
int dy[4] = { 0,1,0,-1 };
int dx[4] = { 1,0,-1,0 };
int ty, tx, y, x;
int maxa, n, m;
int main(void)
{
	int i, j;
	scanf("%d %d", &m, &n);
	int sy, sx;
	int b = 0;
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= m; j++)
		{
			scanf("%d", &a[i][j]);
			if (a[i][j] == 1)
			{
				b++;
				yx[b].first = i;
				yx[b].second = j;
			}
			else
			{
				d[i][j] = INF;
			}
		}
	}
	for (j = 1; j <= b; j++)
	{
		q.push(yx[j].first);
		q.push(yx[j].second);
		d[yx[j].first][yx[j].second] = 0;
		a[yx[j].first][yx[j].second] = 2;
		while (!q.empty())
		{
			y = q.front(); q.pop();
			x = q.front(); q.pop();
			for (i = 0; i <= 3; i++)
			{
				ty = y + dy[i];
				tx = x + dx[i];
				if (ty >= 1 && ty <= n && tx >= 1 && tx <= m && a[ty][tx] != -1 && d[ty][tx] > d[y][x] + 1)
				{
					d[ty][tx] = d[y][x] + 1;
					q.push(ty);
					q.push(tx);
					if (a[ty][tx] != 1)
					{
						a[ty][tx] = 2;
					}
				}
			}
		}
	}
	maxa = -1;
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= m; j++)
		{
			if (maxa < d[i][j])
			{
				maxa = d[i][j];
			}
		}
	}
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= m; j++)
		{
			printf("%d ", d[i][j]);
		}
		printf("\n");
	}
	if (maxa == INF)
	{
		printf("-1");
	}
	else if (maxa == 0)
	{
		printf("0");
	}
	else
	{
		printf("%d", maxa);
	}
	return 0;
}

rnjstpgns91 3년 전 0

질문 올리신 문제가 토마토가 아닌 스도쿠 문제입니다.

rnjstpgns91 3년 전 0

출력해보니 답 이외에 값들도 출력이 됩니다. 배열을 출력하시는 부분을 지우거나 주석처리해보세요.

maxa를 구하는 과정이 이상합니다. 예제 3번을 디버깅 해보세요.

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

문제

문제

출처

ICPC

톰마토마토마톰톰톰톰마톰토토토토마토토마토토토토마톰마토마토마톰톰톰톰마톰토마토

hs9200 3년 전 0

rnjstpgns91 3년 전 0

rnjstpgns91 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말