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 yipilanglbc at 2016-03-14 15:21:37 on Problem 3414
#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
struct State{
    int i, j;
    vector<int> steps;
};
int vis[105][105];
int a, b, c;
void print(vector<int> t)
{
    if(!t.empty())
    {
        cout << t.size() << endl;
        for(int i = 0; i < t.size(); i++)
            if(t[i] == 1)
                cout << "FILL(1)\n";
            else if(t[i] == 2)
                cout << "DROP(1)\n";
            else if(t[i] == 3)
                cout << "POUR(1,2)\n";
            else if(t[i] == 4)
                cout << "FILL(2)\n";
            else if(t[i] == 5)
                cout << "DROP(2)\n";
            else if(t[i] == 6)
                cout << "POUR(2,1)\n";
            else
                continue;
    }
    else
        cout << "impossible\n";
}
void bfs(State p)
{
    queue<State> Q;
    memset(vis, 0, sizeof(vis));
    Q.push(p);
    vis[p.i][p.j] = 1;
    while(!Q.empty())
    {
        State tmp = Q.front();
        Q.pop();
        if(tmp.i == c || tmp.j == c)
        {
            print(tmp.steps);
            return ;
        }
        State np = tmp;
        np.i = a;
        np.j = tmp.j;
        if(!vis[np.i][np.j])
        {
            vis[np.i][np.j] = 1;
            np.steps.push_back(1);
            Q.push(np);
        }
        np = tmp;
        np.i = 0;
        np.j = tmp.j;
        if(!vis[np.i][np.j])
        {
            vis[np.i][np.j] = 1;
            np.steps.push_back(2);
            Q.push(np);
        }
        np = tmp;
        int cha = b - tmp.j;
        if(np.i >= cha)
        {
            np.j = b;
            np.i = tmp.i - cha;
        }
        else
        {
            np.j = tmp.j + tmp.i;
            np.i = 0;
        }
        if(!vis[np.i][np.j])
        {
            vis[np.i][np.j] = 1;
            np.steps.push_back(3);
            Q.push(np);
        }
        np = tmp;
        np.j = b;
        np.i = tmp.i;
        if(!vis[np.i][np.j])
        {
            vis[np.i][np.j] = 1;
            np.steps.push_back(4);
            Q.push(np);
        }
        np = tmp;
        np.j = 0;
        np.i = tmp.i;
        if(!vis[np.i][np.j])
        {
            vis[np.i][np.j] = 1;
            np.steps.push_back(5);
            Q.push(np);
        }
        np = tmp;
        cha = a - tmp.i;
        if(np.j >= cha)
        {
            np.i = a;
            np.j = tmp.j - cha;
        }
        else
        {
            np.i = tmp.j + tmp.i;
            np.j = 0;
        }
        if(!vis[np.i][np.j])
        {
            vis[np.i][np.j] = 1;
            np.steps.push_back(6);
            Q.push(np);
        }
    }
    cout << "impossible\n" << endl;
}
int main()
{
    cin >> a >> b >> c;
    vector<int> q;
    bfs(State{0, 0, q});
    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