글 읽기 - 시간초과 모르겠어요ㅠㅠ

mugol2002 5년 전 0

시간초과가 나는데 어떻게 줄여야될지 모르겠어요ㅠㅠ 제발 도와주세용ㅠㅠ

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

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

queue  q[100001];
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 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;//몇초에서 불붙었는지
				}
				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 (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 (i = 0; i < h; i++) {
				for (j = 0; j < w; j++) {
					if (fire[i][j] == time) {
						for (k = 0; k < 4; k++) {
							if (i + hh[k] >= 0 && i + hh[k] < h && j + ww[k] >= 0 && j + ww[k] < w) {
								if (b[i + hh[k]][j + ww[k]] != '#') {
									if (fire[i + hh[k]][j + ww[k]] == -1) {
										//printf("fire %d %d %d\n", i, j, k);
										fire[i + hh[k]][j + ww[k]] = time + 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년 전 0

상근이를 큐에 넣고 BFS 하듯이, 불도 큐에 넣고 BFS 하세요. 불만 77~78번째 줄처럼 루프를 돌려서 찾을 이유가 없습니다.

mugol2002 5년 전 0

감사합니다!!

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

문제

문제

출처

ICPC

시간초과 모르겠어요ㅠㅠ

mugol2002 5년 전 0

djm03178 5년 전 0

mugol2002 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말