글 읽기 - 런타임에러.....

kioio5 6년 전 1

왜나는걸까요???

visit배열이 너무 커서일까요???ㅠㅠㅠㅠㅠㅠ

16메가인데

충분하다고 생각하는데 ...이유 아시는 분 있으시면 좀 도와주세용.....흙...

---------------

아니군요..

8천만개면 80MB이네요....

어떻게 해결해야할까요.. 도와주십쇼 ㅠㅠ

------------------

해결했습니다.

bool을 bitset으로 처리했습니다.

#include <stdio.h>
#include <iostream>
#include <queue>

#define MAX_SIZE 3
#define ll long long 

using namespace std;

bool visit[876543211];

int tmp[MAX_SIZE][MAX_SIZE];
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int ret;
int zx, zy;


void input(){
	int m = 1;

	for (int i = 0; i < 9; i++){
		ret *= 10;

		int num;
		scanf("%d", &num);
		ret += num * m;

	}
}

int calc(int v, int d){
	int zx, zy;
	for (int i = 2; i >= 0; i--){
		for (int j = 2; j >= 0; j--){
			tmp[i][j] = v % 10;
			v /= 10;
			if (tmp[i][j] == 0) zx = i, zy = j;
		}
	}

	int nx = zx + dx[d];
	int ny = zy + dy[d];

	if (nx < 0 || ny < 0 || nx >= 3 || ny >= 3) return -1;

	swap(tmp[nx][ny], tmp[zx][zy]);

	v = 0;

	for (int i = 0; i < 3; i++){
		for (int j = 0; j < 3; j++){
			v *= 10;
			v += tmp[i][j];
		}
	}

	return v;
}

int bfs(){
	int first = 123456780;

	queue<pair<int, int> > q;

	q.push(make_pair(first, 0));

	while (!q.empty()){
		int map = q.front().first;
		int weight = q.front().second;
		q.pop();

		if (ret == map) return weight;

		if (visit[map]) continue;
		visit[map] = 1;

		for (int i = 0; i < 4; i++){
			int tmp = calc(map, i);
			if (tmp == -1) continue;
			if (visit[tmp]) continue;
			
			q.push(make_pair(tmp, weight + 1));
		}

	}

	return -1;
}

int main(){
	input();
	printf("%d\n", bfs());
	return 0;
}

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

문제

문제

출처

ICPC

런타임에러.....

kioio5 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말