*                                                    *
 * 返回值：無                                         *
 ******************************************************/
{
	printf("((%d %d %d) %f %f)\n", pNode->m, pNode->c, pNode->b, pNode->g, pNode->f);
}

void PrintPath(struct NODE *pGoal) 
/******************************************************
 * 功能：在屏幕上打印解路徑。在搜索過程中，每個節點指 *
 *       向其父節點，從目標節點開始，逆向打印各節點， *
 *       既得到解路徑                                 *
 *                                                    *
 * 入口參數：                                         *
 *   pGoal：指向求解得到的目標節點                    *
 *                                                    *
 * 返回值：無                                         *
 ******************************************************/
{
	if (pGoal == NULL) return;
	PrintPath(pGoal->pFather);	//遞歸
	printf("(%d %d %d)\n", pGoal->m, pGoal->c, pGoal->b);
}

int IsGrandFather(struct NODE *pNode, struct NODE *pFather)
/******************************************************
 * 功能：判斷一個節點是否與自己的祖父節點所表示的狀態 *
 *       一樣                                         *
 *                                                    *
 * 入口參數：                                         *
 *   pNode：指向給定節點的指針                        *
 *   pFather：指向給定節點的父節點的指針              *
 *                                                    *
 * 返回值：當給定節點所表示的狀態與自己的祖父一樣時， *
 *         返回1，否則返回0                           *
 ******************************************************/
{
	if (pFather == NULL) return 0;
	if (pFather->pFather == NULL) return 0;
	return Equal(pNode, pFather->pFather);
}

int IsGoal(struct NODE *pNode)
/******************************************************
 * 功能：判斷給定節點是否為目標節點                   *
 *                                                    *
 * 入口參數：                                         *
 *   pNode：指向給定節點的指針                        *
 *                                                    *
 * 返回值：當給定節點是目標節點時，返回1，否則返回0   *
 ******************************************************/
{
	if (pNode->m == 0 &&
		pNode->c == 0 &&
		pNode->b == 0) return 1;
	else return 0;
}

int Safe(struct NODE *pNode)
/******************************************************
 * 功能：判斷一個狀態是否為安全的，即是否滿足在河的任 *
 *       何一岸，傳教士人數不少于野人人數，或者只有野 *
 *       人而沒有傳教士。對于超出參數范圍的狀態，也認 *
 *       為是不安全的                                 *
 *                                                    *
 * 入口參數：                                         *
 *   pNode：指向給定節點的指針                        *
 *                                                    *
 * 返回值：當給定節點安全時，返回1，否則返回0         *
 ******************************************************/
{
	if (pNode->m < 0 ||
		pNode->c < 0 ||
		pNode->m > M ||
		pNode->c > M) return 0;
	if (pNode->m == M ||
		pNode->m == 0) return 1;
	return (pNode->m == pNode->c);
}

int H_Function(struct NODE *pNode)
/******************************************************
 * 功能：計算給定節點的h值，h = m + c - 2b            *
 *                                                    *
 * 入口參數：                                         *
 *   pNode：指向給定節點的指針                        *
 *                                                    *
 * 返回值：h值                                        *
 ******************************************************/
{
	return pNode->m + pNode->c - 2*pNode->b;
}

struct NODE *A_Star(struct NODE *s)
/******************************************************
 * 功能：A*算法主函數                                 *
 *                                                    *
 * 入口參數：                                         *
 *   s：指向初始節點的指針                            *
 *                                                    *
 * 返回值：指向求解得到的目標節點的指針，或者返回NULL *
 *         表示空間不夠用或者找不到問題的解           *
 ******************************************************/
{
	struct NODE *n = NULL, *m = NULL, *pNode = NULL;
	int i, j;
	g_pOpen = s;	//初始化OPEN表和CLOSED表
	g_pClosed = NULL;
	while (g_pOpen)		//OPEN表不空
	{
		n = g_pOpen;	//取出OPEN表的第一個元素n
		if (IsGoal(n)) return n; //如果n為目標節點，則成功結束
		g_pOpen = g_pOpen->pNext; //否則，從OPEN表中刪除n
		g_pClosed = AddToClosed(n, g_pClosed);	//將n加入到CLOSED中

		// 以下兩重循環，i表示上船的傳教士人數，j表示上船的野人人數
		for (i = 0; i <= K; i++)
		{
			for (j = 0; j <= K; j++)
			{
				if (i + j == 0 ||	//非法的上船組合
					i + j > K ||
					(i != 0 && i < j)) continue;

				if (n->b == 1)	//當船在左岸時
				{
					m = NewNode(n->m-i, n->c-j, 0);	//產生下一個狀態m
				}
				else	//當船在右岸時
				{
					m = NewNode(n->m+i, n->c+j, 1);	//產生下一個狀態m
				}

				if (m == NULL) return NULL;	//如果空間不夠用，則失敗結束

				if (IsGrandFather(m, n) || !Safe(m))	
					//如果m與他的祖父狀態相同，或者是一個非法狀態，則舍棄m
				{
					free(m);
					continue;
				}

				//當m是合法狀態時
				m->pFather = n;	//標記其父節點為n
				m->g = n->g + 1;	//其g值為其父節點的g值加1
				m->f = m->g + H_Function(m);	//計算其f值，f = g+h

				if (pNode = In(m, g_pOpen))	//如果m已經出現在OPEN表中
				{
					if (m->f < pNode->f)	//如果m的f值小于OPEN表中相同狀態的f值
					{
						//則將該節點從OPEN表中刪除，并將m加入到OPEN表中。
						g_pOpen = AddToOpen(m, Del(pNode, g_pOpen));
						free(pNode);
					}
					else	//否則舍棄m
					{
						free(m);
					}
				}
				else if (pNode = In(m, g_pClosed))	//如果m已經出現在CLOSED中
				{
					if (m->f < pNode->f)	//如果m的f值小于CLOSED表中相同狀態的f值
					{
						//則將該節點從CLOSED表中刪除，并重新添加到OPEN表中
						g_pClosed = Del(pNode, g_pClosed);
						g_pOpen = AddToOpen(m, g_pOpen);
						free(pNode);
					}
					else	//否則舍棄m節點
					{
						free(m);
					}
				}
				else	//其他情況，將m加入到OPEN表中
				{
					g_pOpen = AddToOpen(m, g_pOpen);
				}
			}
		}
	}
	//如果OPEN表空了，還沒有找到目標節點，則搜索以失敗結束，
	//返回NULL
	return NULL;	
}

void main(void)
{
	struct NODE *s;
	s = NewNode(M, C, 1);	//設置初始節點
	s = A_Star(s);	//A*搜索
	if (s) PrintPath(s);	//如果找到問題的解，則輸出解路徑
	else printf("找不到問題的解!/n");
	FreeList(g_pOpen);	//釋放動態節點
	FreeList(g_pClosed);
}