bfs求调
  • 板块P1242 新汉诺塔
  • 楼主cgxd
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/2/3 14:16
  • 上次更新2025/2/3 19:45:40
查看原帖
bfs求调
1272259
cgxd楼主2025/2/3 14:16
#include<bits/stdc++.h>
using namespace std;
int n, ans;
typedef array<vector<int>, 4> arr;
arr f, l;
typedef vector<tuple<int, int, int>> vec;
deque<pair<arr, vec>> dq;
set<arr> s;
arr change(arr a, int x, int y){
	a[y].push_back(a[x].back()), a[x].pop_back();
	return a;
}signed main(){
	scanf("%d", &n);
	for(int i = 1; i <= 3; ++i){
		int k;
		scanf("%d", &k);
		while(k--){
			int x;
			scanf("%d", &x);
			f[i].insert(f[i].begin(), x);
		}
	}for(int i = 1; i <= 3; ++i){
		int k;
		scanf("%d", &k);
		while(k--){
			int x;
			scanf("%d", &x);
			l[i].insert(l[i].begin(), x);
		}
	}dq.push_back({f, vec(0, {0, 0, 0})});
	while(dq.size()){
		pair<arr, vec> p = dq[0];
		dq.pop_front();
		arr a = get<0>(p);
		vec v = get<1>(p);
		for(int i = 1; i <= 3; ++i){
			for(int j = 1; j <= 3; ++j){
				if(i == j or a[i].empty()) continue;
				arr a1 = change(a, i, j);
				if(s.count(a1)) continue;
				vec v1 = v;
				v1.insert(v1.begin(), {a1[j].back(), i, j});
				s.insert(a1);
				/*for(vector<int> v: a1){
					for(int i: v) printf("%d ", i);
					puts("");
				}*/if(a1 == l){
					for(tuple<int, int, int> t: v)
						printf("move %d from %c to %c\n", get<0>(t), get<1>(t) + 64, get<2>(t) + 64);
					return printf("%lu", v.size()), 0;
				}dq.push_back({a1, v1});
			}
		}
	}return 0;
}
2025/2/3 14:16
加载中...