글 읽기 - 메모리 초과 질문입니다.

jaehon2002 5년 전 0

메모리 초과 예상 되는 부분은

불의 좌표를 담당하는 fq(큐) 밖에 없는데

finput 함수에서 방문 처리를 하였는데 왜 이러는지 궁금합니다.

----------------------후기------------------------------

이 소스를 올리면서 플레이어 방문처리로 되있던거

if (x < 0 || y < 0 || x >= r || y >= c || map[x][y] == '#' || map[x][y] == 'F' || map[x][y] == 'j') return;

를 발견하고 제대로 수정하고 올렸더니 됐나보네요.

finput이 아니라 pinput이 문제였네요.

감사합니다.

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string.h>
#include <string>
#include <stdlib.h>
#include <algorithm>>
#include <queue>
#include <vector>
#include <functional>
#include <iostream>
#include <string>
#include <time.h>
#include <stack>
#include <math.h>

using namespace std;

int flag;
int r, c;
int result;

int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

char map[1001][1001];

queue <pair<int, int>> q;
queue <pair<int, int>> fq;

void finput(int x, int y)
{
	if (x < 0 || y < 0 || x >= r || y >= c || map[x][y] == '#' || map[x][y] == 'F')
		return;

	map[x][y] = 'F';
	fq.push(make_pair(x, y));
}

void pinput(int x, int y)
{
	if (x < 0 || y < 0 || x >= r || y >= c || map[x][y] == '#' || map[x][y] == 'F' || map[x][y] == 'J')
		return;

	if (x == 0 || y == 0 || x == r - 1 || y == c - 1)
	{
		flag = 1;
		return;
	}

	map[x][y] = 'J';
	q.push(make_pair(x, y));
}

void move()
{
	pair<int, int> tmpf;
	pair<int, int> tmpp;
	int fsize, psize;

	while (1) {

		result++;

		fsize = fq.size();
		psize = q.size();

		for (int i = 0; i < fsize; i++) {
			tmpf = fq.front();

			for (int j = 0; j < 4; j++)
			{
				int nx = tmpf.first + dx[j];
				int ny = tmpf.second + dy[j];
				
				finput(nx, ny);
			}
			
            fq.pop();
		}

		for (int i = 0; i < psize; i++) {
			tmpp = q.front();

			for (int j = 0; j < 4; j++)
			{
				int nx = tmpp.first + dx[j];
				int ny = tmpp.second + dy[j];
                
                pinput(nx, ny);
			}

			q.pop();
		}

		if (flag == 1 || q.size() == 0)
			break;
	}
}

int main() {

	scanf("%d %d", &r, &c);
	for (int i = 0; i < r; i++)
		scanf("%s", map + i);

	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			if (map[i][j] == 'J')
			{
				if (i == 0 || j == 0 || i == r - 1 || j == c - 1)
					flag = 1;
			
				q.push({ i,j });
			}
			else if (map[i][j] == 'F')
			{
				fq.push({ i,j });
			}
		}
	}
	
	if (flag == 1)
	{
		printf("%d\n", result + 1);
		return 0;
	}

	move();
	
	flag == 0 ? printf("IMPOSSIBLE\n") : printf("%d\n", result + 1);

	return 0;
}

djm03178 5년 전 1

이 코드 그대로 제출했더니 2968KB로 잘 통과됩니다.

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

문제

문제

출처

ICPC

메모리 초과 질문입니다.

jaehon2002 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말