글 읽기 - 메모리 초과 원인 뭘까요? ㅠㅠ

leila000 4년 전 0

알고리즘은 맞는거 같은데 메모리 초과가 뜨네요 ㅠㅠ

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
int T, X, Y;
char map[1100][1100];
int dy[4] = { 1,-1,0,0 };
int dx[4] = { 0,0,1,-1 };
struct info { int y, x, t; };
std::vector<info> fire;
int main() {
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++) {
		scanf("%d %d", &X, &Y);
        
		std::queue<info> sang;
		fire.clear();
        // map 입력받고 상근이 위치도 공석으로 바꿈
		for (int i = 1; i <= Y; i++){
			for (int j = 1; j <= X; j++) {
				scanf(" %1c", &map[i][j]);
				if (map[i][j] == '@') {
					sang.push({ i,j,0 });
					map[i][j] = '.';
				}
				if (map[i][j] == '*') fire.push_back({ i,j,0 });
			}
		}
		// map 주위에 0 깔아줌 제 2의 벽같은 느낌으로..
		for (int i = 0; i <= X + 1; i++) {
			map[0][i] = '0'; map[Y + 1][i] = '0';
		}
		for (int i = 0; i <= Y + 1; i++) {
			map[i][0] = '0'; map[i][X+1] = '0';
		}
		bool find = false;
		int nxt_time = 0;
        //BFS
		while (!sang.empty()) {
			info head = sang.front();
			sang.pop();
			if (map[head.y][head.x] == '0') {
				printf("%d\n", head.t);
				find = true;
				break;
			}
//시간 지날 때 마다 fire 위치 갱신 (불 새로 깔아줌)
			if (head.t == nxt_time) {
				std::vector<info> temp;
				for (int i = 0; i < fire.size(); i++) {
					for (int d = 0; d < 4; d++) {
						int ny = fire[i].y + dy[d];
						int nx = fire[i].x + dx[d];
						if (ny<1 || nx<1 || ny>Y || nx>X) continue;
						if (map[ny][nx] == '.') {
							temp.push_back({ ny,nx,head.t + 1 });
							map[ny][nx] = '*';
						}
					}
				}
				fire.clear();
				for (int i = 0; i < temp.size(); i++)
					fire.push_back(temp[i]);
				temp.clear();

				nxt_time++;
			}

//상근이 이동
			for (int d = 0; d < 4; d++) {
				int ny =head.y + dy[d];
				int nx = head.x + dx[d];
				if (map[ny][nx] == '#' || map[ny][nx] == '*') continue;
				sang.push({ ny,nx,head.t + 1 });
			}

		}
		if(!find)
			printf("IMPOSSIBLE\n");
	}
	return 0;
}

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

문제

문제

출처

ICPC

메모리 초과 원인 뭘까요? ㅠㅠ

leila000 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말