12906号新河内塔

3359 ワード
コーディングスキル コーディングテスト テキストリンク
arrayを利用してみましょう
template < typename T, size_t N > class array;
T:データ型
N:パラメータの個数
array arr1 = {1,2,3};//作成して初期化
array arr2;//4つのゴミ値を含む
arrayを使用すると、文字列をより簡単に処理できます.
従って、ハノイタワーを処理するためにarrays;宣伝する
次に、3つの文字列を格納するのではなくdist配列を使用します.
map, int> d;発表する.
#include <iostream>
#include <map>
#include <queue>
#include <array>

using namespace std;

int main() {
	int n;
	array<string, 3> s;
	for (int i = 0; i < 3; i++) {
		cin >> n;
		if (n > 0) cin >> s[i];
		else s[i] = "";
	}
	int cnt[3] = { 0,0,0 };
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < s[i].length(); j++) {
			cnt[s[i][j] - 'A']++;
		}
	}
	map<array<string, 3>, int> d;
	queue<array<string, 3>> Q;
	Q.push(s);
	d[s] = 0; //왜 0이지 -> ch가 아니라 d니까 거리가 0이징
	while (!Q.empty()) {
		array<string, 3> now = Q.front(); Q.pop();
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				if (i == j) continue;
				if (now[i].length() == 0) continue;
				array<string, 3> next = now;
				next[j].push_back(next[i].back());
				next[i].pop_back();
				if (d.count(next) == 0) { //바꿔보장
					d[next] = d[now] + 1;
					Q.push(next);
				}
			}
		}
	}
	array<string, 3> ans;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < cnt[i]; j++) {
			ans[i] += (char)('A' + i);
		}
	}
	cout << d[ans] << '\n';

	return 0;
}
参考資料
https://blockdmask.tistory.com/332
SFMCとその特徴
[BOJ]2056号:ミッション