题解 | #火车进站#

火车进站

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")

全部评论

相关推荐

06-11 17:39
门头沟学院 Java
小呆呆的大鼻涕:卧槽,用户彻底怒了
点赞 评论 收藏
分享
星辰再现:裁员给校招生腾地方
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-18 12:01
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务