글 읽기 - 메모리초과 질문 드립니다

rlarlgns012 7년 전 0

배열에서 초과날거 같지는 않은데

q도 잘 초기화 시킨거 같구요 ㅠㅠ 어디가 문제일까요

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

struct node {
	int x, y;
	int cnt;
};

int X, Y;
char map[1001][1001];
int map_cnt[1001][1001];
bool visited[1001][1001];
int result = 0;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,-1,0,1 };
queue<node> fire;
queue<node> h;

void process() {

	int now = 0;
	while (!h.empty()) {

		now++;
		while (!h.empty()) {

			node tmp = h.front();
			
			if (tmp.cnt == now) break;
			if (tmp.x == 0 || tmp.x == X - 1 || tmp.y == 0 || tmp.y == Y - 1) {
				result = map_cnt[tmp.y][tmp.x] + 1;
				return;
			}
			h.pop();

			for (int i = 0; i < 4; i++) {
				int tx = tmp.x + dx[i];
				int ty = tmp.y + dy[i];

				if (tx >= 0 && ty >= 0 && tx < X && ty < Y
					&& map[ty][tx] == '.') {

					if (visited[ty][tx] == 0) {
						visited[ty][tx] = 1;
						map_cnt[ty][tx] = tmp.cnt + 1;
						h.push({ tx,ty,tmp.cnt + 1 });
					}
					else if (visited[ty][tx] != 2 && map_cnt[ty][tx] > tmp.cnt + 1) {
						map_cnt[ty][tx] = tmp.cnt + 1;
					}
				}

			}
		}

		while (!fire.empty()) {

			node tmp = fire.front();
			if (tmp.cnt == now) break;
			fire.pop();

			for (int i = 0; i < 4; i++) {
				int tx = tmp.x + dx[i];
				int ty = tmp.y + dy[i];

				if (tx >= 0 && ty >= 0 && tx < X && ty < Y
					&& visited[ty][tx] != 2 && map[ty][tx] != '#') {

					fire.push({ tx, ty, tmp.cnt + 1 });
					visited[ty][tx] = 2;
					map_cnt[ty][tx] = 0;
				}

			}
		}
	}
}

void clear(queue<node> &q) {
	queue<node> empty;
	swap(q, empty);
}

int main() {

	int testcase;
	scanf("%d", &testcase);
	while (testcase--) {

		result = 0;
		clear(fire);
		clear(h);

		scanf("%d %d", &X, &Y);
		
		for (int i = 0; i < Y; i++) {
			for (int j = 0; j < X; j++) {
				scanf(" %c", &map[i][j]);
				map_cnt[i][j] = 9999999;
				visited[i][j] = 0;
				if (map[i][j] == '*') {
					visited[i][j] = 2;
					fire.push({ j,i,0 });
					map_cnt[i][j] = 0;
				}
				else if (map[i][j] == '@') {
					visited[i][j] = 1;
					h.push({ j,i,0 });
					map_cnt[i][j] = 0;
				}
			}
		}

		process();

		if (result == 0)
			printf("IMPOSSIBLE\n");
		else
			printf("%d\n", result);
	}
	return 0;
}

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

문제

문제

출처

ICPC

메모리초과 질문 드립니다

rlarlgns012 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말