글 읽기 - 메모리 초과가 뜹니다

pkc4913 5년 전 0

이차원 배열을 할당했지만 저정도 크기로는 절대 128mb가 될수 없다고 생각하는데요..

어디가 문제인가요??

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

char state[251][251];
bool visited[251][251];
int dy[4] = { 1,-1,0,0 };
int dx[4] = { 0,0,-1,1 };
int r, c;

int bfs(pair<int, int> start) {
	queue<pair<int, int>> q;
	q.push(start);
	int vnum = 0; int onum = 0;

	while (!q.empty()) {
		pair<int, int> next = q.front();
		if (!visited[next.first][next.second]) {
			visited[next.first][next.second] = true;
			if (state[next.first][next.second] == 'v') vnum++;
			if (state[next.first][next.second] == 'o') onum++;
		}
		q.pop();
		for (int i = 0; i < 4; i++) {
			int x = next.first + dx[i];
			int y = next.second + dy[i];
			if (state[x][y] == '#' || visited[x][y] == true || x < 0 || y < 0 || x >= r || y >= c) continue;
			q.push(make_pair(x, y));
		}
	}
	
	return vnum >= onum ? -vnum : onum;
}
int main()
{
	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		scanf("%s", state[i]);
	}

	int vnum = 0; int onum = 0;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (!visited[i][j] && state[i][j] != '#') {
				int result = bfs(make_pair(i, j));
				if (result < 0) vnum -= result;
				else  onum += result;
			}
		}
	}
	printf("%d %d", onum, vnum);
}

zinccccc 5년 전 3

queue에서 pop 하는 시점에 visited를 체크하면, pop 되기 전까진 visited가 false이기 때문에 이미 queue에 들어있는 좌표가 중복으로 queue에 삽입될 수 있습니다.

queue에 삽입하자마자 visited를 갱신하면 해결될 것 같습니다.

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

문제

문제

출처

ICPC

메모리 초과가 뜹니다

pkc4913 5년 전 0

zinccccc 5년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말