Почему A * не возвращает наилучший путь для миссионеров-людоедов

Question

Я написал A * реализацию для решения проблемы миссионеров-людоедов. Но по какой-то причине поиск не находит оптимального способа решения проблемы.

Я пробовал другую эвристическую функцию, полагая, что это повысит производительность, но ничего существенного.

#include<bits/stdc++.h>
using namespace std;
class node {
public:
int lc,lm,rc,rm; //number of cannibal and missionaries on left and right  //side respectively
int level;
int cost;
node *parent;
int boat; //boat position. 0 for left side
};

struct comp
{
    bool operator()(const node *l,const node *r)const{
return (l->level+l->cost)>(r->level+r->cost);
}

};

node *newnode(int lc,int lm,int rc,int rm,int level,node *parent,int boat)
{
    node *root=new node();
    root->lc=lc;
    root->rc=rc;
    root->lm=lm;
    root->rm=rm;
    root->level=level;
    root->parent=parent;
    root->boat=boat;
    return root;
}
bool isSafe(int lc,int lm,int rc,int rm)
{
    if(lc<0 || lm<0 || rc<0 || rm<0|| lc>3 || lm>3 || rc<0 || rm<0)
    return false;
    return (lc<=lm || lm==0) && (rc<=rm || rm==0);
}
void printE(node *cur)
{
    int lc=cur->lc;
    int lm=cur->lm;
    int rc=cur->rc;
    int rm=cur->rm;
    for(int i=0;i<lc;i++)
    {
        cout<<"C";
    }
    cout<<" ";
    for(int i=0;i<lm;i++)
    {
        cout<<"M";
    }
    cout<<" -------------- ";
    for(int i=0;i<rc;i++)
    {
        cout<<"C";
    }
    cout<<" ";
    for(int i=0;i<rm;i++)
    {
        cout<<"M";
    }
    cout<<"\n\n";

}
void print(node *cur)
{
    if(cur==NULL)
    return ;
    print(cur->parent);
    printE(cur);
}
int calCost(node *cur)
{
    return (cur->lc+cur->lm)+abs(1-cur->boat);
}

void solve(int lc,int lm,int rc,int rm)
{
    node *m=newnode(lc,lm,rc,rm,0,NULL,0);
    m->cost=calCost(m);
    priority_queue<node *,vector<node *> ,comp> p;
    p.push(m);

    while(!p.empty())
    {
        //cout<<"while"<<endl;
        node *cur=p.top();
        p.pop();
        if(cur->cost==0)
        {

            print(cur);
            return;
        }
        else
        {
            if(cur->boat==0)
            {

                if(isSafe(cur->lc-2,cur->lm,cur->rc+2,cur->rm))
                {
                    //cout<<"left"<<endl;
                    node *n=newnode(cur->lc-2,cur->lm,cur->rc+2,cur->rm,cur->level+1,cur,1);
                    n->cost=calCost(n);
                    p.push(n);

                }

                if(isSafe(cur->lc,cur->lm-2,cur->rc,cur->rm+2))
                {
                    node *n=newnode(cur->lc,cur->lm-2,cur->rc,cur->rm+2,cur->level+1,cur,1);
                    n->cost=calCost(n);
                    p.push(n);
                }
                if(isSafe(cur->lc-1,cur->lm-1,cur->rc+1,cur->rm+1))
                {
                    node *n=newnode(cur->lc-1,cur->lm-1,cur->rc+1,cur->rm+1,cur->level+1,cur,1);
                    n->cost=calCost(n);
                    p.push(n);
                }

                if(isSafe(cur->lc-1,cur->lm,cur->rc+1,cur->rm))
                {
                    //cout<<"left"<<endl;
                    node *n=newnode(cur->lc-1,cur->lm,cur->rc+1,cur->rm,cur->level+1,cur,1);
                    n->cost=calCost(n);
                    p.push(n);

                }

                 if(isSafe(cur->lc,cur->lm-1,cur->rc,cur->rm+1))
                {
                    //cout<<"left"<<endl;
                    node *n=newnode(cur->lc,cur->lm-1,cur->rc,cur->rm+1,cur->level+1,cur,1);
                    n->cost=calCost(n);
                    p.push(n);

                }

            }
            else
            {
                if(isSafe(cur->lc+1,cur->lm,cur->rc-1,cur->rm))
                {
                    node *n=newnode(cur->lc+1,cur->lm,cur->rc-1,cur->rm,cur->level+1,cur,0);
                    n->cost=calCost(n);
                    p.push(n);
                }

                if(isSafe(cur->lc+2,cur->lm,cur->rc-2,cur->rm))
                {
                    node *n=newnode(cur->lc+2,cur->lm,cur->rc-2,cur->rm,cur->level+1,cur,0);
                    n->cost=calCost(n);
                    p.push(n);                   
                }

                if(isSafe(cur->lc,cur->lm+1,cur->rc,cur->rm-1))
                {
                    node *n=newnode(cur->lc,cur->lm+1,cur->rc,cur->rm-1,cur->level+1,cur,0);
                    n->cost=calCost(n);
                    p.push(n);                    
                }

                if(isSafe(cur->lc,cur->lm+2,cur->rc,cur->rm-2))
                {
                    node *n=newnode(cur->lc,cur->lm+2,cur->rc,cur->rm-2,cur->level+1,cur,0);
                    n->cost=calCost(n);
                    p.push(n);                   
                }

                if(isSafe(cur->lc+1,cur->lm+1,cur->rc-1,cur->rm-1))
                {
                    node *n=newnode(cur->lc+1,cur->lm+1,cur->rc-1,cur->rm-1,cur->level+1,cur,0);
                    n->cost=calCost(n);
                    p.push(n);                   
                }
            }            
        }        
    }
}
int main()
{
    int lc=3 ,lm=3,rc=0,rm=0;
    solve(lc,lm,rc,rm);
}

Я не могу понять, почему она не дает оптимальный путь. Спасибо.