车车题
Nostopathy
·
·
题解
P1139
每辆车的调度次数为 1 \sim 3 次，故枚举调度次数 n \sim 3n 进行搜索。只要能调度到下一位置就进行调度。
1. 路线是单向的，故到达出口就不能返回，每次判断若到达出口则跳出。
2. 若剩余调度次数小于还没到出口的车数，则不能满足。
3. 若当前位置没有车，直接跳出。
代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pb push_back
const int N = 30;
int n, g[N], s[4][N], c[N], sta, l[N], r[N], a[N];
string str;
void d(int x) {
if(s[3][c[3]]!=g[c[3]] || sta-x+1<c[0]+c[1]+c[2])
return;
if(x==sta+1 && !c[0]+c[1]+c[2]) {
for(int i=1; i<x; ++i)
cout<<char(a[i]+'a'-1)<<" "<<char(l[i]+'A')<<" "<<char(r[i]+'A')<<"\n";
exit(0); //直接结束程序
}
if(x>sta)
return;
for(int i=0; i<=2; ++i)
for(int j=i+1; j<=3 && c[i]; ++j) {
int t=s[i][c[i]--];
a[x]=s[j][++c[j]]=t;
l[x]=i;
r[x]=j;
d(x+1);
s[i][++c[i]]=t;
--c[j]; //回溯
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>str;
str=" "+str;
for(int i=1; i<=n; ++i)
g[n-i+1]=str[i]-'a'+1, s[0][++c[0]]=i;
for(sta=n; sta<=n*3; ++sta)
d(1);
cout<<"NO";
return 0;
}
```
题解来之不易，麻烦点赞再走~