/*
有一條河，河的左岸有m個傳教士（Missionary）和m個野人（Cannibal），和一艘最多可乘n人的小船。約定左岸，右岸和船上或者沒有傳教士，或者野人數量少于傳教士，否則野人會把傳教士吃掉。
版權yuan_chuan

*/

#include?
#include?

#define?MAXM?10
#define?MAXC?5

typedef?struct?mc_state
{
????int?m_num;
????int?c_num;
????int?boat_state;
????int?g;
????int?h;
????int?f;
????struct?mc_state?*next;
????struct?mc_state?*parent;
}mc_state;

mc_state?*open;
mc_state?*close;

mc_state?boat[8]={{011000NULLNULL}
????{021000NULLNULL}
????{031000NULLNULL}
????{101000NULLNULL}
????{111000NULLNULL}
????{201000NULLNULL}
????{211000NULLNULL}
????{301000NULLNULL}
};
/*建立一個新的狀態結點*/
mc_state?*?new_mc_state（void）
{
????mc_state?*p;
????p=（struct?mc_state?*）malloc（sizeof（struct?mc_state））;
????p->m_num=0;
????p->c_num=0;
????p->boat_state=1;
????p->g=0;
????p->h=0;
????p->f=0;
????p->next=NULL;
????p->parent=NULL;
}
/*顯示open表close表狀態*/
int?show（mc_state?*p）
{
????if?（p==NULL）
????{
????????printf（“空表沒有元素!“）;
????}
????while?（p!=NULL）
????{
????????printf（“（?%d?%d?%d?f=%d?）\n“p->m_nump->c_nump->boat_statep->f）;
????????p=p->next;
????}

}
/*判斷是否存在于open或closed表中*/
int?exist（mc_state?*pmc_state?*head）
{
????mc_state?*q*prior;
????q=head;
????if?（q==NULL）
????{
????????return?0;
????}
????else
????{
????????while?（?q!=NULL）
????????{
????????????if?（?（p->m_num?==?q->m_num）&&（p->c_num?==?q->c_num）&&（p->boat_state?==?q->boat_state））
????????????{
????????????????return?1;
????????????}
????????????q=q->next;
????????}
????????return?0;
????}
}

/*open表添加*/
int?add_open（mc_state?*p）
{
????mc_state?*q*r;
????q=open;

????if?（q==NULL）
????{
????????open?=?p;
????}
????else
????{
????????if?（?p->f?<=?q->f?）
????????{
????????????p->next?=?open;
????????????open?=?p;
????????}
????????else
????????{
????????????r=q;

????????????while?（q!=NULL?&&?q->f?f）
????????????{
????????????????r=q;
????????????????q=q->next;
????????????}
????????????q=r->next;
????????????r->next=p;
????????????p->next=q;
????????}
????}
????return?1;
}
/*open表刪除*/
mc_state?*?del_open（?）
{
????mc_state?*p;
????if?（open==NULL）
????{
????????return?NULL;
????}
????else
????{
????????p=open;
????????open?=?p?->next;
????????return?p;
????}
}

/*close表添加*/
int?add_close（mc_state?*p）
{
????if?（close==NULL）
????{
????????close=p;
????}
????else
????{
????????p->next=close;
????????close=p;
????}
????return?1;
}
/*啟發函數*/
int?h（mc_state?*p）
{
????return?p->m_num+p->c_num-2*p->boat_state;
}
/*判斷狀態是否合法*/
int?is_mc_state（mc_state?*p）
{
????if?（（p->m_num>MAXM）||
????????????（p->m_num<0）||
????????????（p->c_num>MAXC）||
????????????（p->c_num<0））
????{
????????return?0;
????}
????else
????{
????????if?（（（p->m_num>=p->c_num）&&
????????????????（MAXM?-?p->m_num?>=?MAXC?-?p->c_num）
????????????）||
????????????????（p->?m_num==MAXM）?||
?????????????