Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

用bfs搜然后建树过了(~ ̄▽ ̄)~

Posted by xiaoming10086 at 2019-11-05 20:23:51 on Problem 3414
//找到答案直接从子节点向上找然后输出就好了
#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int a, b, c;
bool ava = false;
bool vis[101][101];
struct tree
{
    tree* father;
    int op;
    tree(tree* father, int op) : father(father), op(op) {}
};
struct node
{
    int a;
    int b;
    tree* t;
};
queue<node> q;

tree* bfs()
{
    while(!q.empty())
    {
        tree *father = q.front().t;
        int anow = q.front().a;
        int bnow = q.front().b;
        q.pop();
        node n;
        for(int i = 0; i < 6; i++)
        {
            int anext = anow;
            int bnext = bnow;
            switch(i)
            {
                case 0:
                {
                    if(anow < a)
                    {
                        anext = a;
                    }
                    break;
                }
                case 1:
                {
                    if(anow)
                    {
                        anext = 0;
                    }
                    break;
                }
                case 2:
                {
                    if(anow)
                    {
                        if(anow + bnow <= b)
                        {
                            bnext = anow + bnow;
                            anext = 0;
                        }
                        else
                        {
                            anext = anow + bnow - b;
                            bnext = b;
                        }
                    }
                    break;
                }
                case 3:
                {
                    if(bnow < b)
                    {
                        bnext = b;
                    }
                    break;
                }
                case 4:
                {
                    if(bnow)
                    {
                        bnext = 0;
                    }
                    break;
                }
                case 5:
                {
                    if(bnow)
                    {
                        if(anow + bnow <= a)
                        {
                            anext = anow + bnow;
                            bnext = 0;
                        }
                        else
                        {
                            bnext = anow + bnow - a;
                            anext = a;
                        }
                    }
                    break;
                }
            }
            if(!vis[anext][bnext])
            {
                vis[anext][bnext] = true;
                node n;
                n.a = anext;
                n.b = bnext;
                n.t = new tree(father, i);
                if(anext == c || bnext == c)
                {
                    ava = true;
                    return n.t;
                }
                q.push(n);
            }
        }
    }
    return NULL;
}

string findd(int n)
{
    switch(n)
    {
        case 0:
            return "FILL(1)";
        case 1:
            return "DROP(1)";
        case 2:
            return "POUR(1,2)";
        case 3:
            return "FILL(2)";
        case 4:
            return "DROP(2)";
        case 5:
            return "POUR(2,1)";
    }
}

void outPut(tree *t, int n)
{
    if(t->father == NULL)
    {
        cout << n << endl;
        cout << findd(t->op) << endl;
        return;
    }
    outPut(t->father, n + 1);
    cout << findd(t->op) << endl;
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(vis, false, sizeof(vis));
    vis[0][0] = true;
    cin >> a >> b >> c;
    if(c == a)
    {
        cout << 1 << endl;
        cout << "FILL(1)" << endl;
        return 0;
    }
    else if(c == b)
    {
        cout << 1 << endl;
        cout << "FILL(2)" << endl;
        return 0;
    }
    while(!q.empty())
    {
        q.pop();
    }
    node n;
    n.a = a;
    n.b = 0;
    n.t = new tree(NULL, 0);
    q.push(n);
    n.b = b;
    n.a = 0;
    n.t = new tree(NULL, 3);
    q.push(n);
    vis[0][b] = true;
    vis[a][0] = true;
    tree* t = bfs();
    if(!ava)
    {
        cout << "impossible";
    }
    else
    {
        outPut(t, 1);
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator