글 읽기 - 시간초과 제에에에발 알려주세요 ㅠㅠ

minhye11 4년 전 0

각 i = 1, 2, ... P개의 점에 대해서 순서대로
s[i]번의 확장 개수만큼 와일문 돌리고
castle[i]에 대해서 네 방향으로 확장시켜줬는데요. (확장시켜준 기준점은 pop()해줌)
S[i]가 커서 생기는 문제인가요ㅠㅠ

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

int N, M, P;
char board[1000][1001];/*0~~*/
int is_searched[1000][1000];
int temp_searched[1000][1000];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
vector <int> s;/*1~~~ 최대 확장 가능*/
queue <pair<int, int> > castle[10];/*1~~~ 각 점에서 확장하는 점들*/
int number_counts[10];

int main() {
	cin >> N >> M >> P;
	s.push_back(0);
	for (int i = 1; i <= P; i++) {
		int a;
		cin >> a;
		s.push_back(a);
	}
	for (int i = 0; i < N; i++) {
		cin >> board[i];
		for (int j = 0; j < M; j++) {
			for (int k = 1; k <= P; k++) {
				if (board[i][j] == k + '0') {
					castle[k].push({ i, j });
					is_searched[i][j] = k;
				}
				else if (board[i][j] == '#') is_searched[i][j] = 10;
			}
		}
	}
	while (true) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				temp_searched[i][j] = is_searched[i][j];
			}
		}

		for (int i = 1; i <= P; i++) {
			int check = s[i];
			while (check) {
				int check2 = castle[i].size();
				while (check2) {
					int x = castle[i].front().first;
					int y = castle[i].front().second;
					for (int j = 0; j < 4; j++) {
						int nx = x + dx[j];
						int ny = y + dy[j];
						if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
						if (is_searched[nx][ny] != 0) continue;
						is_searched[nx][ny] = is_searched[x][y];
						castle[i].push({ nx, ny });
					}
					castle[i].pop();
					check2--;
				}
				check--;
			}
		}

		int checker = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (is_searched[i][j] != temp_searched[i][j]) checker++;
			}
		}
		if (checker == 0) break;
	}
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			int v = is_searched[i][j];
			if(v != 10 && v != 0) number_counts[v]++;
		}
	}
	for (int i = 1; i <= P; i++) {
		cout << number_counts[i] << " ";
	}
}

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

문제

문제

출처

ICPC

시간초과 제에에에발 알려주세요 ㅠㅠ

minhye11 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말