글 읽기 - 시간초과 질문입니다.

crowjhd 6년 전 0

시간초과가 나는데 어지 해결해야 하나요??ㅜㅜ

#include <cstdio>
#include <queue>
#include <iostream>

using namespace std;
int M, N;
int map[1000][1000];
int visit[1000][1000];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
int a, b;
int c, d;

queue<pair<int, int>> q;


int bfs()
{
	int count = 0;

	while (1)
	{
		int num_zero = 0;
		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++)
			{
				if (map[i][j] == 1 && visit[i][j]==0)
				{
					q.push(make_pair(i, j));
					visit[i][j] = 1;
				}
				else if (map[i][j] == 0)
					num_zero++;
			}

		if (num_zero == 0)
		{

			return count;
		}
		while (!q.empty())
		{

			a = q.front().first;
			b = q.front().second;
			q.pop();

			for (int i = 0; i < 4; i++)
			{
				c = a + dx[i];
				d = b + dy[i];

				if (map[c][d] == 0 && visit[c][d]==0 && c<N && d<M && 0<=c && 0<=d)
				{
					map[c][d] = 1;

				}
			}
		}
		printf("a= %d, b= %d, count= %d \n",a,b, count);
		count++;
	}
}


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

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
		{
			scanf("%d", &map[i][j]);

		}
	printf("%d",bfs());
	printf("\n");
}

milkpekoe 6년 전 0

5 5
0 0 0 0 0
0 -1 -1 -1 0
0 -1 1 -1 0
0 -1 -1 -1 0
0 0 0 0 0

이런값 넣어보셨나요?

익은 토마토가 비어있는 토마토에 둘러 쌓여있습니다.

이 경우 결과는 -1이죠

무한히 도네요

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

문제

문제

출처

ICPC

시간초과 질문입니다.

crowjhd 6년 전 0

milkpekoe 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말