글 읽기 - 시간초과 원인

jsh 7년 전 0

이 소스에서 시간초과가 나는 원인을 알고 싶습니다

#include <iostream>
#include <queue>

using namespace std;

char g[1002][1002];
int col, row, chk[1002][1002], f[1002][1002];
int dir[4][2] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };

void init() {
	col = 0, row = 0;
	for (int i = 0; i < 1002; i++) {
		for (int j = 0; j < 1002; j++) {
			g[i][j] = 0;
			chk[i][j] = 0;
			f[i][j] = -1;
		}
	}
}

void fire(int sec) {
	queue<pair<int, int> > que;
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			if (f[i][j] == sec) que.push(make_pair(i, j));
		}
	}
	while (!que.empty()) {
		int nowR = que.front().first;
		int nowC = que.front().second; que.pop();
		for (int i = 0; i < 4; i++) {
			int nR = nowR + dir[i][0];
			int nC = nowC + dir[i][1];

			if (nR < 0 || nC < 0 || nR >= row || nC >= col) continue;
			if (g[nR][nC] == '#' || g[nR][nC] == '*') continue;
			f[nR][nC] = sec+1;
		}
	}
}

int bfs(int r, int c) {
	queue<pair<int, int> > que;
	que.push(make_pair(r, c));
	chk[r][c] = 1;

	while(!que.empty()) {
		int nowR = que.front().first;
		int nowC = que.front().second; que.pop();

		if (nowR == 0 || nowC == 0 || nowR == (row - 1) || nowC == (col - 1)) {
			return chk[nowR][nowC];
		}

		fire(chk[nowR][nowC]);
		for (int i = 0; i < 4; i++) {
			int nR = nowR + dir[i][0];
			int nC = nowC + dir[i][1];

			if (nR < 0 || nC < 0 || nR >= row || nC >= col) continue;
			if (g[nR][nC] == '#') continue;
			if (f[nR][nC] != -1 && (f[nR][nC] <= chk[nowR][nowC] + 1)) continue;
			if (chk[nR][nC] != 0 && chk[nR][nC] <= chk[nowR][nowC] + 1) continue;

			chk[nR][nC] = chk[nowR][nowC] + 1;
			que.push(make_pair(nR, nC));
		}
	}
	return -1;
}
int main() {
	int tc = 0; 
	cin >> tc;
	while (tc--) {
		init();
		int sR = 0, sC = 0;
		cin >> col >> row;
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				cin >> g[i][j];
				if (g[i][j] == '@') {
					sR = i, sC = j;
				}
				else if (g[i][j] == '*') {
					f[i][j] = 1;
				}
			}
		}

		int ans = bfs(sR, sC);
		if (ans == -1) {
			cout << "IMPOSSIBLE" << '\n';
		}
		else {
			cout << ans << '\n';
		}

	}
	return 0;
}

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

문제

문제

출처

ICPC

시간초과 원인

jsh 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말