题解 | #火车进站#
火车进站
https://www.nowcoder.com/practice/97ba57c35e9f4749826dc3befaeae109
#include <iostream>
#include <stack>
#include <vector>
#include <map>
using namespace std;
int n;
int a[10];
vector<int> state1; //出站火车状态表示
stack<int> state2; //在站中的火车
int state3 = 1; //还未进站的火车，当前枚举到第几辆车
map<string, int> mp; //存储最后结果，自动排序
void dfs()
{
if(state1.size() == n)
{
string res;
for(auto t : state1)
{
res += t + '0';
res += ' ';
}
mp[res] = 1;
return;
}
//在车站中栈顶火车只两种选择：一个是出栈一个是不出栈，不出栈也就是右边火车进栈
if(state2.size())
{
state1.push_back(state2.top());
state2.pop();
dfs();
state2.push(state1.back());//恢复现场
state1.pop_back();
}
if(state3 <= n)
{
state2.push(a[state3 ++] );
dfs();
state2.pop();
state3 --;
}
}
int main() {
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
dfs();
for(auto t : mp) cout << t.first << endl;
return 0;
}
// 64 位输出请用 printf("%lld")
投递大疆等公司7个岗位