글 읽기 - 시간초과 해결해주세요ㅜㅜㅜ

mugol2002 5년 전 0

시간초과ㅠㅠㅠ불도 따로했는데 계속 이러는 이유를 모르겠어요...

#pragma warning(disable: 4996)
#include <stdio.h>

typedef struct _q {
	int q_h;
	int q_w;
	int t;
} queue;

typedef struct _f {
	int f_h;
	int f_w;
	int t;
} firee;

firee f[1000001];
int f_f = 0;
int f_l = 0;
queue q[1000001];
int q_f = 0;
int q_l = 0;
int w, h;
char b[1001][1001];
int memo[1001][1001];
int fire[1001][1001];
int ww[4] = { 1, -1, 0, 0 };
int hh[4] = { 0, 0, 1, -1 };
int flag;
int min;

int main() {
	int t;
	int k, i, j;
	int m_h, m_w;
	int p_h, p_w;
	int fp_h, fp_w;
	int time;

	scanf("%d", &t);
	for (k = 0; k < t; t++) {
		flag = -1;
		min = 100001;
		scanf("%d %d", &w, &h);
		getchar();
		for (i = 0; i < h; i++) {
			for (j = 0; j < w; j++) {
				memo[i][j] = 100001;
				fire[i][j] = -1;
			}
		}
		for (i = 0; i < h; i++) {
			for (j = 0; j < w; j++) {
				scanf("%c", &b[i][j]);
				if (b[i][j] == '*') {
					fire[i][j] = 0;//몇초에서 불붙었는지
					f[f_f].f_h = i;
					f[f_f].f_w = j;
					f[f_f].t = 0;
					f_f++;
				}
				if (b[i][j] == '@') {
					m_h = i;
					m_w = j;
				}
			}
			getchar();
		}

		q[q_f].q_h = m_h;
		q[q_f].q_w = m_w;
		q[q_f].t = 0;
		q_f++;
		memo[m_h][m_w] = 0;

		//불 번지기
		
		while (f_l != f_f) {
			//pop
			p_h = f[f_l].f_h;
			p_w = f[f_l].f_w;
			time = f[f_l].t;
			f_l++;
			//restrict
			for (k = 0; k < 4; k++) {
				if (p_h + hh[k] >= 0 && p_h + hh[k] < h && p_w + ww[k] >= 0 && p_w + ww[k] < w) {
					if (b[p_h + hh[k]][p_w + ww[k]] != '#') {
						if (fire[p_h + hh[k]][p_w + ww[k]] == -1) {
							//printf("fire %d %d %d\n", p_h, p_w, time);
							fire[p_h + hh[k]][p_w + ww[k]] = time + 1;
							f[f_f].f_h = p_h + hh[k];
							f[f_f].f_w = p_w + ww[k];
							f[f_f].t = time + 1;
							f_f++;
						}
					}
				}
			}
		}
		


		while (q_l != q_f) {
			//pop
			p_h = q[q_l].q_h;
			p_w = q[q_l].q_w;
			time = q[q_l].t;
			q_l++;
			//printf("%d %d %d\n", p_h, p_w, time);
			//탈출조건
			if (p_h == 0 || p_h == h - 1 || p_w == 0 || p_w == w - 1) {
				if (min > time + 1) {
					min = time + 1;
				}
				flag = 1;
			}

			//인접한 노드
			
			for (k = 0; k < 4; k++) {
				if (p_h + hh[k] >= 0 && p_h + hh[k] < h && p_w + ww[k] >= 0 && p_w + ww[k] < w) {
					//printf("1 %d\n", k);
					if (b[p_h + hh[k]][p_w + ww[k]] != '#') {
						//printf("2 %d %d\n", k, fire[m_h + hh[k]][m_w + ww[k]]);
						if (fire[p_h + hh[k]][p_w + ww[k]] == -1 || fire[p_h + hh[k]][p_w + ww[k]] > time + 1) {
							//printf("3 %d\n", k);
							if (memo[p_h + hh[k]][p_w + ww[k]] > time + 1) {
								//printf("4 %d\n", k);
								//push
								q[q_f].q_h = p_h + hh[k];
								q[q_f].q_w = p_w + ww[k];
								q[q_f].t = time+1;
								q_f++;
								memo[p_h + hh[k]][p_w + ww[k]] =time+1;
							}

						}
					}
				}
			}



		}
		

		if (flag == -1) {
			printf("IMPOSSIBLE\n");
		}
		else {
			printf("%d\n", min);
		}

	}
	
	return 0;
}

djm03178 5년 전 1

로컬에서도 안 돌아갈 것 같네요. 프로그램이 정상 종료되는지는 해보셨나요?

40번째 줄에서 k가 t까지 돌아야 되는데 t가 증가하고 있고, 심지어 이 k는 루프 안쪽에서 다른 루프에도 쓰이고 있습니다. 다른 변수를 사용해서 t번 돌리세요.

그리고 min과 memo 초기값도 너무 작습니다. 최대 약 50만까지 나올 수 있습니다.

마지막으로, 큐들의 시작과 끝을 나타내는 변수들을 매 루프마다 초기화해줘야 합니다.

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

문제

문제

출처

ICPC

시간초과 해결해주세요ㅜㅜㅜ

mugol2002 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말