글 읽기 - 시간초과 문제..

apdh25 5년 전 0

어떻게 수정해야 시간초과를 피할 수 있을까용..?

#include <iostream>
#include <queue>

using namespace std;

typedef pair<int, int> Pair;

const int MAX = 101;

int GP[MAX][MAX];
bool visited[MAX][MAX];
int day[MAX][MAX];

queue<Pair>q;

int bfs(int m, int n, int total_size)
{
	int ripe_size = q.size();

	while (q.empty() != true)
	{
		Pair pair = q.front();
		q.pop();
		
		if (ripe_size == total_size) {
			return day[pair.first][pair.second] + 1;
		}

		for (int i = 1; i <= 4; i++)
		{
			int first = pair.first;
			int second = pair.second;

			switch (i)
			{
			case 1:
				second -= 1;
				break;
			case 2:
				second += 1;
				break;
			case 3:
				first += 1;
				break;
			case 4:
				first -= 1;
				break;
			}

			if (((first<1 || first>n) || (second<1 || second>m)) || visited[first][second] == true || GP[first][second] == -1)
				continue;
			else {
				visited[first][second] = true;
				q.push(Pair(first, second));
				GP[first][second] = 1;
				day[first][second] = day[pair.first][pair.second] + 1;
				ripe_size++;
			}
		}
	}
	return -1;
}

int main()
{
	int m, n, size;
	scanf("%d %d", &m, &n);

	size = m * n;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%d", &GP[i][j]);

			if (GP[i][j] == 1)
			{
				q.push(Pair(i, j));
				visited[i][j] = true;
			}
			else if (GP[i][j] == -1) size -= 1;
		}
	}
	if (q.size() == size)
	{
		printf("0\n");
		return 0;
	}
	printf("%d\n", bfs(m, n, size));
	return 0;
}

lovinix 5년 전 0

이 코드 제대로 돌아가나요?

2<=M,N<=1000 인데 MAX를 101로 잡으셨습니다.

apdh25 5년 전 0

그것도 그렇고 bfs 함수의 동작과정 자체에 문제가 있었네요 ㅎㅎ.. 소중한댓글 달아주셔서 감사합니다

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

문제

문제

출처

ICPC

시간초과 문제..

apdh25 5년 전 0

lovinix 5년 전 0

apdh25 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말