글 읽기 - 어디가 틀린지 모르겠습니다ㅠ

maro7913 4년 전 0

어디가 틀린지 모르겠습니다ㅠ

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

int zero;
int puzle;

int cnt;
void bfs() {
	string pstr;	
	map<string, int> m;
	int d[4] = { -3,3,-1,1 };
	queue<string> q;
	pstr = to_string(puzle);
	q.push(pstr);
	m[pstr] = 0;
	while (!q.empty()) {
		int size = q.size();
		for (int a = 0; a < size; a++) {
			string stmp = q.front(); q.pop();

			if (stmp == "123456780"){
				cout << cnt;
				return;
			}				
			string st;
			zero = stmp.find('0');
			for (int i = 0; i < 4; i++) {
			if (((zero%3==2)&&d[i]==1)||((zero%3==0)&&d[i]<0)) {
								continue;
							}
			st = stmp;

				int tmp;
				tmp = zero + d[i];
				if (tmp < 0 || tmp>8) continue;
			
				else {
					swap(st[tmp], st[zero]);
					if (m.count(st)) {
					continue;
				    }
					m[st] = 1;

					q.push(st);
				}
			}

		}//end for
		cnt++;
	}//end while
	cnt = -1;
	cout<< cnt;
	return;
}//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;
}

maro7913 4년 전 0

해결했습니다.

123456780으로 두고 풀었을 때,

arr[2]와 arr[3], arr[5]와 arr[6]이 이동이 되면 안되는데 이동이 됐었습니다.

이 부분 잡아주니 풀렸습니다.

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

int zero;
int puzle;

int cnt;
void bfs() {
	string pstr;	
	map<string, int> m;
	int d[4] = { -3,3,-1,1 };
	queue<string> q;
	pstr = to_string(puzle);
	q.push(pstr);
	m[pstr] = 0;
	while (!q.empty()) {
		int size = q.size();
		for (int a = 0; a < size; a++) {
			string stmp = q.front(); q.pop();
			if (stmp == "123456780"){
				cout << cnt;
				return;
			}				
			string st;
			zero = stmp.find('0');
			for (int i = 0; i < 4; i++) {
				if (((zero % 3 == 2) && i == 3) || ((zero % 3 == 0) && i==2)) { 
					continue; }

				int tmp;
				tmp = zero + d[i];
				if (tmp < 0 || tmp>8) continue;
				
				else {st = stmp;
					swap(st[tmp], st[zero]);
					if (m.count(st)) {
					continue;
					}
					m[st] = 1;

					q.push(st);
				}
			}

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

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

문제

문제

출처

ICPC

어디가 틀린지 모르겠습니다ㅠ

maro7913 4년 전 0

maro7913 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말