题目 – luoguP1139

考虑暴搜，不停尝试A到B、A到C、A到D、B到C、B到D、C到D，尝试顺序正好是按照字典序。但暴搜会炸，发现总的操作次数最少为$n$（每辆火车直接A到D），最多为$3n$（每辆火车都A到B、B到C、C到D），于是类似迭代加深搜索地去限制总的操作次数进行搜索，遇到可行的方案就输出答案后强制exit。还要加一些可行性剪枝，不然会TLE。

void dfs(int k, int m){
	if(k > m){
		if(cnt[3] < n) return ; // 已经操作了m次却还没调度完
		for(auto v : ans){
			cout << (char)(v.h + 'a') << ' ';
			cout << (char)(v.l + 'A') << ' ';
			cout << (char)(v.r + 'A') << '\n';
		}
		exit(0); // 强制exit
	}
	if(cnt[3] && a[3][cnt[3]] != s[n - cnt[3]] - 'a') return ; // D处顺序有硬性要求，一处不对就剪掉
	if(m - k + 1 < cnt[0] + cnt[1] + cnt[2]) return ; // 剩下的即使都直接向D处移，剩余操作次数也不够了
	for(int i = 0; i <= 2; i++){ // 0-A, 1-B, 2-C
		if(!cnt[i]) continue; // i处没有火车，也就不用调度
		for(int j = i + 1; j <= 3; j++){ // 只能从左向右单向开
			a[j][++cnt[j]] = a[i][cnt[i]--]; // i -> j
			ans.push_back({a[j][cnt[j]], i, j}); // 存操作
			dfs(k + 1, m);
			a[i][++cnt[i]] = a[j][cnt[j]--]; // j -> i 回溯
			ans.pop_back(); // 回溯操作
		}
	}
}
int main(){
	cin >> n >> s;
	for(int i = 0; i < n; i++) a[0][++cnt[0]] = i; // 一开始A-0处有火车a-0, b-1, c-2...
	for(int i = n; i <= 3 * n; i++) dfs(1, i);
	cout << "NO\n"; // 没有方案
	return 0;
}

后话

迭代加深搜索 + 可行性剪枝，提高组级别的dfs题。