글 읽기 - 메모리 초과

maro7913 4년 전 0

왜 메모리 초과가 나는지 모르겠습니다.ㅠㅠ

#include<iostream>
#include<queue>
#include<vector>
#include<cmath>
#include<string>
#include<algorithm>
#include<map>
using namespace std;

vector<int> chk(9, 0);
int zero;
int puzle;
string pstr;
int cnt;
void bfs() {
	map<string, int> m;
	int d[4] = { -3,3,-1,1 };
	queue<pair<string,int>> q;
	pstr = to_string(puzle);
	q.push(make_pair(pstr,zero));
	m[pstr] = 0;
	while (!q.empty()) {
		int size = q.size();
		for (int a = 0; a < size; a++) {
			pair<string, int> stmp = q.front(); q.pop();
			if (!stmp.first.compare("123456780")) {
				cout << cnt;
				return;
			}
			zero = stmp.second;
			for (int i = 0; i < 4; i++) {
				pair<string, int>st=stmp;
				int tmp;
				tmp = zero + d[i];
				if (tmp < 0 || tmp>8) continue;

				swap(st.first[tmp], st.first[zero]);
				if (m.count(st.first)) continue;
				st.second = tmp;
				q.push(st);
			}

		}//end for
		cnt++;
	}//end while
	cnt = -1;
}//end bfs()
int main() {
	int tmp;
	for (int i = 0; i < 9; i++) {
		cin >> tmp;
		if (!tmp) zero = i;
		puzle = puzle * 10+tmp;
	}
	bfs();
	return 0;
}

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

문제

문제

출처

ICPC

메모리 초과

maro7913 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말