Demo entry 6359922

py

   

Submitted by anonymous on Apr 30, 2017 at 15:05
Language: C++. Code size: 5.4 kB.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <string>
#include <set>
#include <vector>
#include <queue>
#include <map>
using namespace std;


const int BottleNum=4;
int pre[100000000];
struct node
{
    int num,step;
};

typedef map< vector<int> ,node > mymap;//
set< vector<int> > statemap;//IDDFS

vector<int> Volumn;//每个瓶子的容积
vector<vector<int> > path(1000);//路径
vector<int> init;//初始态
vector<int> target;//目标态
int maxdeep;//最大搜索深度
int StateNum;//状态对应编号
bool found;//是否找到可行解
map< int ,vector<int> > ExistState;//用编号输出相应状态
map< vector<int> ,node > VecNum;//每个状态用一个结构体存,结构体里放编号和最短路径


bool cmp(vector<int> a,vector<int> b)
{
    return VecNum[a].step>VecNum[b].step;
}

int reach(vector<int> now)
{
    int ans=0;
    for (int i=0;i<now.size();i++) if (now[i]!=target[i]) ans++;
    return ans;
}

struct state
{
    vector<int> Bottle;
    int step;
    state()
    {
        step=0;
        Bottle.resize(BottleNum);
    }
    state(vector<int> now)
    {
        for (int i=0;i<now.size();i++) Bottle[i]=now[i];
    }
};

bool judge(vector<int > now,vector<int > target)
{
    for (int i=0;i<target.size();i++) if (target[i]!=now[i]) return false;
    return true;
}

void ShowVector(vector<int> v)
{
    for (int i=0;i<v.size();i++) printf("%2d ",v[i]);
    printf("\n");
}

void pour(int &a,int &b,const int &va,const int &vb)//pour i to j
{
    if (a>vb-b)
    {
        a=a-(vb-b);
        b=vb;
    }
    else
    {
        b=b+a;
        a=0;
    }
}

void bfs(vector<int> Start)
{
    VecNum[Start].num=++StateNum;
    ExistState[StateNum]=Start;
    pre[StateNum]=0;
    state cur,nex;
    queue<state> q;
    cur.Bottle=Start;cur.step=0;
    q.push(cur);
    while (!q.empty())
    {
        cur=q.front();q.pop();
        for (int i=0;i<BottleNum;i++)
        {
            if (cur.Bottle[i]==0) continue;//this bottle is empty, no need to go on
            for (int j=0;j<BottleNum;j++)
            {
                nex=cur;nex.step++;
                if (i==j) continue;
                pour(nex.Bottle[i],nex.Bottle[j],Volumn[i],Volumn[j]);//pour Bottle[i] to Bottle[j]
                if (VecNum.find(nex.Bottle)==VecNum.end())//状态判重
                {
                    VecNum[nex.Bottle].num=++StateNum;//将状态映射到一个编号
                    VecNum[nex.Bottle].step=nex.step;//保存到达此状态所需要的步数
                    ExistState[StateNum]=nex.Bottle;//存储当前状态
                    pre[StateNum]=VecNum[cur.Bottle].num;//保存当前状态的前驱
                    q.push(nex);
                }
            }
        }
    }
}

void SetInitialVolumn()
{
    int v[BottleNum]={12,10,6,3};
    Volumn.insert(Volumn.end(),v,v+BottleNum);
}

void SetInitialState()
{
    int a[BottleNum]={12,0,0,0};
    init.insert(init.end(),a,a+BottleNum);
}

void SetTarget()
{
    int a[BottleNum]={4,4,4,0};
    target.insert(target.end(),a,a+BottleNum);
}

void ShowAllPossibleTarget()
{
    int cnt=0;
    for (mymap::iterator it=VecNum.begin();it!=VecNum.end();it++)
    {
        printf("STATE %d\n",++cnt);
        for (int i=0;i<it->first.size();i++) printf("%2d ",(it->first)[i]);
        printf("STEP = %2d\n",it->second.step);
        printf("\n");
    }
}

void PrintTargetPath(vector<int> tar)
{
    vector<vector<int> >path;
    int p=VecNum[tar].num;
    do
    {
        path.push_back(ExistState[p]);
        p=pre[p];
    }
    while (p!=0);
    int cnt=0;
    for (int i=path.size()-1;i>=0;i--)
    {
        printf("STEP %d: ",++cnt);
        for (int j=0;j<path[i].size();j++)
        {
            printf("%2d ",path[i][j]);
        }
        printf("\n");
    }
}

void ShowGreater()
{
    sort(bigger.begin(),bigger.end(),cmp);
    for (int i=0;i<bigger.size();i++)
    {
        printf("STEP = %d ",VecNum[bigger[i]].step);
        for (int j=0;j<bigger[i].size();j++)
        {
            printf("%2d ",bigger[i][j]);
        }
        printf("\n");
    }
}

void PrintPossiblePath(int dep)
{
    for (int i=0;i<=dep;i++)
    {
        for (int j=0;j<path[i].size();j++)
        {
            printf("%2d ",path[i][j]);
        }
        printf("\n");
    }
    printf("\n\n");
}

void IDDFS(int dep,vector<int> cur)
{
    vector<int> nex;
    path[dep]=cur;
    if (dep>maxdeep) return;
    if (dep+2>maxdeep && reach(cur)>=3) return;
    if (reach(cur)==0)
    {
        found=true;
        PrintPossiblePath(dep);
        return;
    }
    for (int i=0;i<BottleNum;i++)
    {
        if (cur[i]==0) continue;//this bottle us empty, no need to go on
        for (int j=0;j<BottleNum;j++)
        {
            nex=cur;
            if (i==j) continue;
            pour(nex[i],nex[j],Volumn[i],Volumn[j]);//pour Bottle[i] to Bottle[j]
            dfs(dep+1,nex);
        }
    }
}

void IDAStar()
{
    ShowVector(init);
    ShowVector(target);
    while (!found)
    {
        maxdeep++;
        printf("maxdeep = %d\n",maxdeep);
        dfs(0,init);
    }
}

int main()
{
//    freopen("Find13Bu.txt","w",stdout);
    SetInitialVolumn();
    SetInitialState();
    SetTarget();
//    ShowAllPossibleTarget();
//    bfs(init);
//    ShowGreater();
//    for (int i=0;i<bigger.size();i++) PrintTargetPath(bigger[i]);
    IDAStar();
    return 0;
}

This snippet took 0.02 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).