//****************************************
//* 文件名稱：8_1.cpp                    *
//* 功    能：預定義函數                 *
//* 工作方式：通過主函數調用執行         *
//****************************************
#include "head.h"

//***************************************************
//* 函數原型：bool isEmptyOfOPEN()                  *
//* 功    能：判斷是否滿足結束條件                  *
//* 參    數：void                                  *
//* 返 回 值：bool                                  *
//* 工作方式：通過主函數中調用執行                  *
//***************************************************
bool isEmptyOfOPEN()
{ 
	for(unsigned int i=0;i<node_v.size();i++)//node_v.size() 返回容器中實際數據的個數
	{  
		if(node_v[i].outofopen==false) 
			return false; 
	} 
	return true; 
}



//************************************************************
//* 函數原型：bool isEqual(int index, int digit[][COL])      *
//* 功    能：判斷是否達到終止狀態                           *
//* 參    數：(int,int)                                      *
//* 返 回 值：bool                                           *
//* 工作方式：通過主函數中調用執行                           *
//************************************************************
bool isEqual(int loc,int digit[][COL]) 
{ 
	for(int i=0;i<ROW;i++) 
		for(int j=0;j<COL;j++) 
		{ 
			if(node_v[loc].digit[i][j]!=digit[i][j])//判斷是否完全匹配 
				return false; 
		} 
		return true; 
} 

//******************************************************************
//* 函數原型：void PrintSteps(int index, vector<Node>& rstep_v)    *
//* 功    能：輸出整個過程的中間步驟                               *
//* 參    數：(int,vector<Node> &)                                 *
//* 返 回 值：bool                                                 *
//* 工作方式：通過主函數中調用執行                                 *
//****************************************************************** 
void PrintSteps(int loc, vector<Node>& rstep_v) 
{ 
	rstep_v.push_back(node_v[loc]);//將目標節點存放到容器rstep_v中
	int index=node_v[loc].index;//指明目標節點的父節點
	while (index!=0) 
	{ 
		rstep_v.push_back(node_v[index]); 
		index=node_v[index].index; 
	}//指明中間節點的父節點
	for (int i=(int)rstep_v.size()-1;i>=0;i--) 
		cout<<"步驟"<<rstep_v.size()-i<<endl<<rstep_v[i]<<endl;//輸出整個過程的中間步驟 
} 

//****************************************
//* 文件名稱：8_2.cpp                    *
//* 功    能：預定義函數                 *
//* 工作方式：未找到目標時執行相應操作   *
//****************************************


//********************************************************
//* 函數原型：void Swap(int& a, int& b)                  *
//* 功    能：空格的轉移(即空格與相應元素的交換)         *
//* 參    數：(int&,int&)                              *
//* 返 回 值：void                                       *
//* 工作方式：通過void ProcessNode(int)調用執行          *
//********************************************************
void Swap(int& a, int& b)
{ 
	int t; 
	t=a; 
	a=b; 
	b=t; 
} 

//********************************************************
//* 函數原型：void Assign(Node& node, int index)         *
//* 功    能：完成兩個節點間的復制                       *
//* 參    數：(Node&,int&)                              *
//* 返 回 值：void                                       *
//* 工作方式：通過void ProcessNode(int)調用執行          *
//********************************************************
void Assign(Node& node, int loc)
{ 
	for(int i=0;i<ROW;i++) 
		for(int j=0;j<COL;j++) 
			node.digit[i][j]=node_v[loc].digit[i][j]; 
} 

//********************************************************
//* 函數原型：bool isExpandable(Node& node)              *
//* 功    能：判斷該節點是否可以再擴展                   *
//* 參    數：Node&                                      *
//* 返 回 值：bool                                       *
//* 工作方式：通過void ProcessNode(int)調用執行          *
//********************************************************
bool isExpandable(Node& node)
{ 
	for(unsigned int i=0;i<node_v.size();i++) 
	{ 
		if(isEqual(i,node.digit))//判斷節點是否已經在close表、open表(即容器)中放置
			return false; 
	} 
	return true; 
} 

//************************************************
//* 函數原型：void ProcessNode(int index)        *
//* 功    能：未找到目標時執行相應操作           *
//* 參    數：int                                *
//* 返 回 值：void                               *
//* 工作方式：通過主函數調用執行                 *
//************************************************
void ProcessNode(int loc) 
{ 
	int x=0,y=0; 
	bool flag;//判斷空格是否搜索到空格位置的標記 
	for(int i=0;i<ROW;i++) 
	{ 
		for(int j=0;j<COL;j++)
		{ 
			if(node_v[loc].digit[i][j]==0) 
			{ 
				x=i;y=j; 
				flag=true; 
				break; 
			} 
			else flag=false; 
		} 
		if(flag) 
			break; 
	} 
	/*********************空格上移操作*******************/
	Node node_up; 
	Assign(node_up,loc); 
	if(x>0)//空格不在最上面一行
	{ 
		Swap(node_up.digit[x][y],node_up.digit[x-1][y]);//空格與其上面的元素調換 
		if(isExpandable(node_up)) 
		{ 
		
			node_up.index=loc;//父節點就是剛擴展的節點 
			node_up.outofopen=false;
			node_v.push_back(node_up);//將剛擴展的節點壓到容器中(也可以理解為close表中) 
		} 
	} 
	/*********************空格下移操作*******************/
	Node node_down; 
	Assign(node_down,loc); 

	if(x<2)//空格不在最下面一行
	{ 
		Swap(node_down.digit[x][y],node_down.digit[x+1][y]); //空格與其下面的元素調換 
		if(isExpandable(node_down))
		{ 
		
			node_down.index=loc; //父節點就是剛擴展的節點
			node_down.outofopen=false;
			node_v.push_back(node_down); //將剛擴展的節點壓到容器中(也可以理解為close表中)
		} 
	} 
	/*********************空格左移操作*******************/
	Node node_left; 
	Assign(node_left,loc); 

	if(y>0) //空格不在最左邊一列
	{ 
		Swap(node_left.digit[x][y],node_left.digit[x][y-1]);//空格與其左邊的元素調換 
		if(isExpandable(node_left)) 
		{ 
			node_left.index=loc; //父節點就是剛擴展的節點
			node_left.outofopen=false;
			node_v.push_back(node_left); //將剛擴展的節點壓到容器中(也可以理解為close表中)
		} 
	} 
	/*********************空格右移操作*******************/
	Node node_right; 
	Assign(node_right,loc); 

	if(y<2) //空格不在最右邊一行
	{ 
		Swap(node_right.digit[x][y],node_right.digit[x][y+1]);//空格與其右邊的元素調換  
		if(isExpandable(node_right)) 
		{ 
			node_right.index=loc; //父節點就是剛擴展的節點
			node_right.outofopen=false;
			node_v.push_back(node_right); //將剛擴展的節點壓到容器中(也可以理解為close表中)
		} 
	} 
	
	node_v[loc].outofopen=true;//將父節點放到close表中
}