您现在的位置是:首页 > 学习之路 > ACM||算法ACM||算法

POJ-3087 Shuffle'm Up

卞振伟2019-07-25【ACM||算法】人已围观

简介POJ-3087 Shuffle'm Up
DFS
两副扑克牌按规律洗牌,给出目标牌组,输出需要洗牌多少次得到目标牌组
记录状态,若之前存在过,即跳出(失败)

#include <map>
#include <iostream>
#include <queue>
#include <cstdio>

using namespace std;

int a[5];
int c;
map<pair<int,int> ,int> mp;
map<pair<int,int> ,int> d;
map<char, string> ans;

void bfs(){
    queue<pair<int,int> > q;
    queue<string> path;
    mp[make_pair(0, 0)] = 1;
    q.push(make_pair(0,0));
    path.push("");
    while(!q.empty()){
        pair<int,int> p;
        p = q.front();
        q.pop();
        string s = path.front();
        path.pop();
        if(p.first == c || p.second == c){
            cout<<d[p]<<endl;
            for(int i = 0; i < s.size(); ++i){
                cout<<ans[s[i]]<<endl;
            }
            return ;
        }
        if(p.first < a[0]){
            if(!mp.count(make_pair(a[0], p.second))){
                q.push(make_pair(a[0], p.second));
                d[make_pair(a[0], p.second)] = d[p] + 1;
                mp[make_pair(a[0], p.second)] = 1;
                path.push(s+"1");
            }
            if(p.second){
                int v1 = p.second + p.first > a[0] ? a[0] : p.second + p.first;
                int v2 = p.second + p.first > a[0] ? p.second + p.first - a[0] : 0;
                if(!mp.count(make_pair(v1, v2))){
                    q.push(make_pair(v1, v2));
                    d[make_pair(v1, v2)] = d[p] + 1;
                    mp[make_pair(v1, v2)] = 1;
                    path.push(s+"2");
                }
            }
        }
        if(p.second < a[1]){
            if(!mp.count(make_pair(p.first, a[1]))){
                q.push(make_pair(p.first, a[1]));
                d[make_pair(p.first, a[1])] = d[p] + 1;
                mp[make_pair(p.first, a[1])] = 1;
                path.push(s+"3");
            }
            if(p.first){
                int v2 = p.second + p.first > a[1] ? a[1] : p.second + p.first;
                int v1 = p.second + p.first > a[1] ? p.second + p.first - a[1] : 0;
                if(!mp.count(make_pair(v1, v2))){
                    q.push(make_pair(v1, v2));
                    d[make_pair(v1, v2)] = d[p] + 1;
                    mp[make_pair(v1, v2)] = 1;
                    path.push(s+"4");
                }
            }
        }
        if(p.first){
            if(!mp.count(make_pair(0, p.second))){
                q.push(make_pair(0, p.second));
                d[make_pair(0, p.second)] = d[p] + 1;
                mp[make_pair(0, p.second)] = 1;
                path.push(s+"5");
            }
        }
        if(p.second){
            if(!mp.count(make_pair(p.first, 0))){
                q.push(make_pair(p.first, 0));
                d[make_pair(p.first, 0)] = d[p] + 1;
                mp[make_pair(p.first, 0)] = 1;
                path.push(s+"6");
            }
        }
    }
    cout<<"impossible"<<endl;
}

int main(){
    ans['1'] = "FILL(1)";
    ans['2'] = "POUR(2,1)";
    ans['3'] = "FILL(2)";
    ans['4'] = "POUR(1,2)";
    ans['5'] = "DROP(1)";
    ans['6'] = "DROP(2)";
    while(cin>>a[0]>>a[1]>>c){
        if(a[0] == c || a[1] == c){
            cout<<1<<endl;
            if(a[0] == c)
                cout<<"FILL(1)"<<endl;
            else
                cout<<"FILL(2)"<<endl;
            continue; 
        }
        if(a[0] < c && a[1] < c){
            cout<<"impossible"<<endl;
            continue;
        }
        d.clear();
        mp.clear();
        bfs();
    }
    return 0;
}

Tags:ACM   编程   个人   题解   算法   C|C++

很赞哦! ()

上一篇:POJ-3126 Prime Path

下一篇:POJ-3414 Pots

文章评论

站点信息

  • 建站时间:2018-11-25
  • 网站程序:帝国CMS7.5
  • 文章统计:118篇文章
  • 标签管理标签云
  • 统计数据百度统计
  • 网站地图XML网站地图
  • 微信公众号:扫描二维码,关注我的公众号
  • GitHub:扫描二维码,关注我的GitHub

客服在线

QQ客服

客服微信扫码

服务时间

周一至周日 9:00-21:00