글 읽기 - 메모리초과 ㅠㅠㅠㅠ

gktgnjftm 6년 전 0

메모리 초과 날 이유가 잘 안보이는거같은데 왜 나는지 감이 잘 안오네요 ㅠㅠ

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
char board[1002][1002];
int t, n, m;
bool firevisited[1002][1002];
int dist[1002][1002];
typedef pair <int, int> P;
queue <P> fireq;
queue <P> q;
queue <P> firetemp;
queue <P> temp;
int gox[4] = {0,-1,1,0};
int goy[4] = {1,0,0,-1};
void bfs() {
	while (!q.empty()) {
		while (!fireq.empty()) {
			int firex = fireq.front().first;
			int firey = fireq.front().second;
			fireq.pop();
			for (int i = 0; i < 4; i++) {
				int firenx = firex + gox[i];
				int fireny = firey + goy[i];
				if (firenx<1 || firenx>n || fireny<1 || fireny>m || board[firenx][fireny] == '#' || board[firenx][fireny]=='*') continue;
				else if(!firevisited[firenx][fireny]){
					firevisited[firenx][fireny] = true;
					firetemp.push({ firenx,fireny });
					board[firenx][fireny] = '*';
				}
			}
		}
			while (!firetemp.empty()) {
				int nx = firetemp.front().first;
				int ny = firetemp.front().second;
				fireq.push({ nx,ny });
				firetemp.pop();
			}

			while (!q.empty()) {
				int x = q.front().first;
				int y = q.front().second;
				q.pop();
				for (int i = 0; i < 4; i++) {
					int nx = x + gox[i];
					int ny = y + goy[i];
					if (nx<1 || nx>n || ny<1 || ny>m ||  board[nx][ny] == '#' || board[nx][ny]=='*') continue;
					else if(!firevisited[nx][ny]){
						temp.push({ nx,ny });
						dist[nx][ny] = dist[x][y] + 1;
					}
				}
			}
			while (!temp.empty()) {
				int nx = temp.front().first;
				int ny = temp.front().second;
				q.push({ nx,ny });
				temp.pop();
			}
	}
	while (!q.empty()) { q.pop();}
	while (!fireq.empty()) { fireq.pop();}
}

int main(){
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &m, &n);
		int Min = 999999999;
		memset(firevisited, false, sizeof(firevisited));
		memset(dist, 0, sizeof(dist));
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				scanf(" %c", &board[i][j]);
				if (board[i][j] == '*') {
					fireq.push({ i,j });
					firevisited[i][j] = true;
				}
				else if (board[i][j] == '@') q.push({ i,j });
			}
		}
		bfs();
		for (int j = 1; j <= m; j++) {
			if (dist[1][j]) Min = min(dist[1][j], Min);
			else continue;
		}
		for (int j = 1; j <= m; j++) {
			if (dist[n][j]) Min = min(dist[n][j], Min);
			else continue;
		}
		for (int i= 1; i<= n; i++) {
			if (dist[i][1]) Min = min(dist[i][1], Min);
			else continue;
		}
		for (int i = 1; i <= n; i++) {
			if (dist[i][m]) Min = min(dist[i][m], Min);
			else continue;
		}
		if (Min == 999999999) printf("IMPOSSIBLE\n");
		else printf("%d\n", Min+1);
	}
	return 0;
}

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

문제

문제

출처

ICPC

메모리초과 ㅠㅠㅠㅠ

gktgnjftm 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말