mark

24点运算

http://www.nowcoder.com/questionTerminal/7e124483271e4c979a82eb2956544f9d

#include<bits/stdc++.h>
using namespace std;

map<string, int> table;
vector<int> path(4, 0);
vector<char> vis(4, false);
bool found = false;

void init(map<string, int>& table) {
    for(int i = 2; i <= 10; i++) table[to_string(i)] = i;
    table["A"] = 1; 
    table["J"] = 11;
    table["Q"] = 12;
    table["K"] = 13;
}
string id(int x) { for(auto it : table) if(it.second == x) return it.first; return "NAN";}

bool dfs(vector<int>& num, vector<char>& ops, int begin, int result) {
    if(begin == num.size() && result == 24) {
        stringstream ss;

        ss << id(path[0]) << ops[0] 
           << id(path[1]) << ops[1]
           << id(path[2]) << ops[2] << id(path[3]);

        cout << ss.str() << endl;
        found = true;
        return true;
    }

    for(int i = 0; i < num.size(); i++) {
        if(vis[i]) continue;

        vis[i] = true;
        path[begin] = num[i];
        {
            ops[begin-1] = '+';
            if(dfs(num, ops, begin+1, result + path[begin])) return true;

            ops[begin-1] = '-';
            if(dfs(num, ops, begin+1, result - path[begin])) return true;

            ops[begin-1] = '*';
            if(dfs(num, ops, begin+1, result * path[begin])) return true;

            ops[begin-1] = '/';
            //if(result % path[begin] == 0)
            if(dfs(num, ops, begin+1, result / path[begin])) return true;
        }
        vis[i] = false;
    }

    return false;
}

int main(void)
{
#ifndef ONLINE_JUDGE
    ifstream cin("in.txt");
#endif

    init(table);
    string str[4];

    while(cin >> str[0] >> str[1] >> str[2] >> str[3]) {
        vector<int> num;
        for(auto s : str) if(table.count(s)) num.push_back(table[s]);
        if(num.size() != 4) {cout << "ERROR" << endl; continue;}

        vector<char> ops(3);

        for(int i = 0; i < 4; i++) {
            path[0] = num[i];

            vis[i] = true;
            if(dfs(num, ops, 1, path[0])) break;
            vis[i] = false;
        }
        if(!found) cout << "NONE" << endl;
    }

    return 0;
}
全部评论

相关推荐

点赞 评论 收藏
分享
不要停下啊:大二打开牛客,你有机会开卷了,卷起来,去找课程学习,在牛客上看看大家面试笔试都需要会什么,岗位有什么需求就去学什么,努力的人就一定会有收获,这句话从来都经得起考验,像我现在大三了啥也不会,被迫强行考研,炼狱难度开局,啥也不会,找工作没希望了,考研有丝丝机会
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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