글 읽기 - 시간초과의 원인을 모르겠습니다..

ukjinlee 4년 전 0

dum[i] 라는배열이 S[i] 배열이고 이 배열이 커질수 있기 때문에 Qsize와 count 를 사용하여 두번 확인하고 탈출하게끔 코딩하였습니다.. 그렇게 해도 계속 시간초과가 일어나서 원인을 모르겠습니다

감사합니다.

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int n, m, p;
int dx[] = { 0,0,-1,1 };
int dy[] = { 1,-1,0,0 };
char map[1001][1001];
bool visit[1001][1001];
queue<pair<int,int>> Q[10];
int ar[11];
int dum[10];
int count;
int main()
{
	scanf("%d %d %d", &n, &m, &p);
	int count = n * m;
	for (int i = 1; i <=p; i++)
		scanf("%d", dum+i);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			scanf(" %c", &map[i][j]);
			if (map[i][j] == '#') {
				count--;
			}
			else if (map[i][j] != '.') 
			{
				Q[map[i][j] - '0'].push(make_pair(i,j));
				ar[map[i][j]-'0']++;
				count--;
			}
		}
	for (int i = 1;; i++)
	{
		if (count ==0) break;
		if (i > p)
			i = 1;
		if (!Q[i].size()) continue;
		int cnt = dum[i];
		while (cnt--) 
		{
			if (count == 0) break;
			visit[Q[i].front().first][Q[i].front().second] = true;
			char cc = i + '0';
			int Qsize = Q[i].size();
			if (Qsize == 0) break;
			while (Qsize--)
			{
				int x = Q[i].front().first;
				int y = Q[i].front().second;
				Q[i].pop();
				for (int j = 0; j < 4; j++)
				{
					int nx = x + dx[j];
					int ny = y + dy[j];
					if (nx<1 || ny<1 || nx>n || ny>m) continue;
					if (map[nx][ny] == '.' && !visit[nx][ny])
					{
						ar[i]++;
						Q[i].push(make_pair(nx, ny));
						visit[nx][ny] = true;
						map[nx][ny] = cc;
						count--;
					}
				}
			}
		}
	}
	for (int i = 1; i <=p; i++)
		printf("%d ", ar[i]);
}

nahwasa 4년 전 1

일단 내용 전에 입출력 부분 시간부터 줄여보시는게 좋을 듯 합니다.

https://www.acmicpc.net/blog/view/56

https://www.acmicpc.net/blog/view/57

요 두개 보시면 속도차이가 꽤 크고,

해당 문제는 입력값이 매우 많을 가능성이 있는 문제라 요거부터 처리해보셔야할듯해요!

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

문제

문제

출처

ICPC

시간초과의 원인을 모르겠습니다..

ukjinlee 4년 전 0

nahwasa 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말