//此文件定義了棋盤類
#include "_ChessB.h"
#include <math.h>
#include<graphics.h>
#include<conio.h>
#include<iostream.h>
/* 棋盤的初始化，參數為棋盤所在區域左上角的橫、縱坐標和該區域的高度、寬度 */
_ChessBoard::_ChessBoard(int left,int top,int height,int width)		// 參數為棋盤左上角的坐標
{									// 和棋盤的高度和寬度
	float distance,radius,lheight,startx,starty,topx,topy;
	struct _Nodes TempNodes[200];					// 臨時的節點數組,用來存儲最初生成的所有結點
	distance=(height/17.0)*2/sqrt(3);   	   			// 因為總共有17行,所以distance即為相鄰節點圓心之間的距離
	radius=distance*0.35;                 				// 半徑
	lheight=height/17.0;               				// 行距
	topx=left+width*0.5;						// 最上面的結點的橫坐標的絕對坐標值
	topy=top+(height/17.0)*0.5;					// 最上面的結點的縱坐標的絕對坐標值
	int lineheight;			
	int j,i,t=0;
	head=tail=NULL;							// 構造函數初始化head和tail為空
	
	/* 賦予臨時數組中的每個元素位置坐標 */
	for(i=0;i<13;i++)						// 從上到下、從下到上進行13行，
									// 保證含蓋了所有的節點
	{
		startx=topx-(i)*distance/2;				// 第i行的初始橫坐標
		starty=topy+(i)*lheight;				// 第i行的初始縱坐標
		for(j=0;j<=i;j++)					// 為第i行的各個結點賦坐標
		{
			TempNodes[t].cood.x=startx+j*distance;		// 第i行的第j個節點的橫坐標
			TempNodes[t++].cood.y=starty;			// 第i行的第j個節點的縱坐標
			TempNodes[t].cood.x=TempNodes[t-1].cood.x;	// 第17-i行的第j個節點的橫坐標
			TempNodes[t++].cood.y=topy+(16-i)*lheight;	// 第17-i行的第j個節點的縱坐標
		}
	}
	for(i=t;i< 200;i++)  						// 把臨時數組的剩余節點的的橫縱
									// 坐標設為無效值(1000)
		TempNodes[i].cood.x=TempNodes[i].cood.y=1000;

	cut(TempNodes,t);						// 將臨時數組中相同的元素去掉一個（置坐標值為無效值1000）
	sort(TempNodes);						// 將臨時數組中的元素進行排序并標記序號
	
	int a=0.5*distance;						// 用于兩行的起始橫坐標的計算
	int b=lheight;							// 行距
	int m[6][2]={{2*a,0},{a,b},{-a,b},{-2*a,0},{-a,-b},{a,-b}};	// 相鄰節點坐標的變換值,從最右側開始,順時針變換
	joint(Nodes,m);							// 連接所有結點
}

/* 刪掉具有相同坐標的節點之一 */
void _ChessBoard::cut(struct _Nodes *p,int t )				// 參數為指向棋盤的指針和有效的節點數
{
	int i,j,k=0;
	for (i=0;i< t-1;++i)
	{
		if( p[i].cood.x!=0&& p[i].cood.y!=0)
		for (j=i+1;j< t;++j)
		{
			/* 如果i點的橫縱坐標和j點的橫縱坐標重合(3為誤差值)
					則將j點的橫縱坐標設為無效值(刪掉此點) */
			if (abs(p[i].cood.x-p[j].cood.x)< 3&&abs(p[i].cood.y-p[j].cood.y)<3)
			{
				p[j].cood.x=1000;
				p[j].cood.y=1000;
				break;					// 只可能有一次相同，所以找到后就應該跳出本次循環
			}
		}
	}
}

//對數組中的元素進行排序，按照y、x從小到大排序
void _ChessBoard::sort(struct _Nodes *p){
	struct _Nodes node;
	int j,i,MinIndex,t=0;
	for(i=0;i<182;i++)
		if(p[i].cood.x<800&&p[i].cood.y<800)
			Nodes[t++]=p[i];				// 記錄有效節點于Nodes數組中

	for(i=0;i<120;i++)						// 選擇法排序
	{
		MinIndex=i;
		for(j=i;j<121;j++)
		{
			if(Nodes[j].cood.y-Nodes[MinIndex].cood.y>2)	// Nodes[j]所在行為Nodes[MinIndex]
									// 所在行的下一行,則跳出這層循環
				continue;  						
			if(Nodes[j].cood.y-Nodes[MinIndex].cood.y<-2)
				MinIndex=j; 				// Nodes[j]所在行為Nodes[MinIndex]
									// 所在行的上一行,則用j替換MinIndex 
			else if(Nodes[j].cood.x<Nodes[MinIndex].cood.x) // 若Nodes[j]所在行和Nodes[MinIndex]
									// 所在行為同一行,則若Nodes[j]的橫坐標小于
				MinIndex=j; 				// Nodes[MinIndex]時,用j置換MinIndex;
		}
									// 把坐標最小的結點依次放在Nodes數組的最前面
		node=Nodes[i],Nodes[i]=Nodes[MinIndex],Nodes[MinIndex]=node;
	}
									// 對于每個數組元素的index賦予序號，
									// 從0開始共有121個序號
	for (i=0;i<121;i++)
		Nodes[i].index=i;
}

/* 將每一個節點與相鄰節點連接起來 */
void _ChessBoard::joint(struct _Nodes *q,int (*p)[2])			// p指針接受傳來得m數組
{
	int i,j,k;
	for (i=0;i<121;++i)
		for (j=0;j<6;++j)
		{
			for (k=0;k<121;++k)
			{
									// 判斷i節點和k節點是否為鄰近點,
									// 是則i節點的一個指針指向k結點
				if (abs((q[i].cood.x+p[j][0])-q[k].cood.x)<3&&
						abs((q[i].cood.y+p[j][1])-q[k].cood.y)<3)
				{
					q[i].pointers[j]=&q[k];
					break;
				}
			}
			if(k==121) Nodes[i].pointers[j]=NULL;		// k==121則沒有找到i結點的鄰近點,
									// 則其pointers指針值空
		}
}

/* 按選擇對棋盤進行棋子的初始化 */
int **_ChessBoard::Reset()		
{
	countstep=0;							// 記錄已走棋的步數
	while(head!=NULL)						// 如果頭指針不為空，則釋放已經
	{								// 存在的空間
		head=head->next;
		delete head->before;
	}
	/* 搜索開始時所有標志位清零,棋盤沒有某一方的棋子(Chessman=0),沒有選擇要走的棋子(sellect=0) */
	for(int i=0;i<121;i++)
	{
		Nodes[i].visited=0;
		Nodes[i].sellect=0;
		Nodes[i].Chessman=0;
	}
	int a[2][10]={   						// 20個棋子的初始序號	
			{0,1,2,3,4,5,6,7,8,9},                          // 上（游戲者1）
			{111,112,113,114,115,116,117,118,119,120},      // 下（游戲者2）
			};
	int **c;
	/* c為指向一個指針數組,數組里的每個元素指向一個代表一個游戲方的數組,里面包括
		游戲者序號和10個棋子的節點序號 */
	c=new int*[2];
	for(int k;k<2;k++)
	{
		c[k]=new int[11];					
	}
	c[0][0]=1;							// 為參與游戲的2個游戲者分配棋子
	c[1][0]=2;
	for(i=0;i<10;i++)
	{
		Nodes[c[0][i+1]=a[0][i]].Chessman=1;			// 激活最上的10個棋子為游戲者1
		Nodes[c[1][i+1]=a[1][i]].Chessman=2;			// 激活最下的10個棋子為游戲者2
	}
	return c;							// 返回包含游戲者信息的數組
}

/* 判斷選子是否合法 */
int _ChessBoard::JudgeSellect(int gamerID,int sellect)
{
	if(Nodes[sellect].Chessman==gamerID)
	{								// 如果合法
		for(int i=0;i<121;i++)					// 先將所有的節點標志清零
			Nodes[i].sellect=0;
		Nodes[sellect].sellect=1;				// 選定該子
		return 1;
	}
	else return 0;
}

/* 用深度優先搜索搜索從節點序號start到節點序號end是否存在路徑，并記錄在road數組中 */
int _ChessBoard::DFS(int start,int end)
{
	_Nodes *Node=NULL;
	Nodes[start].visited=1;						// 起始點start被訪問,visited置1
	road[++Nowroad]=start;						// 用road[]數組存儲路徑
	if(Nodes[start].index==end)					// 如果start結點就是end結點則返回1
		return 1;
	else									//否則搜索start周圍的6個指針
		for(int i=0;i<6;i++)					// 遍歷一個結點的周圍六個結點
		{
			Node=Nodes[start].pointers[i];
			if(Node==0||Node->pointers[i]==0)		// 此方向沒有節點，則跳出本次循環
				continue;
			if(Node->Chessman!=0&&Node->pointers[i]->Chessman==0&&Node->pointers[i]->visited==0)//此方向可以走棋
			{
				if(DFS(Node->pointers[i]->index,end))	// 遞歸調用，搜尋可以走棋的路徑
					return 1;
			}
		}
	Nowroad--;							// 如果不存在路徑則Nowroad減1,退回
	return 0;							// 未找到路徑，返回
}

/* 判斷棋子能否從start走到end,能夠的話則同時記錄路徑于數組road中，第一個參數為游戲者序號 */
int _ChessBoard::JudgeMove(int gamerID,int start,int end)
{
	/* instant為start與end節點兩圓心之間的距離的平方,用于判斷start與end是否相鄰 */
	int instant=abs(Nodes[start].cood.x-Nodes[end].cood.x)*abs(Nodes[start].cood.x-Nodes[end].cood.x)+abs(Nodes[start].cood.y-Nodes[end].cood.y)*abs(Nodes[start].cood.y-Nodes[end].cood.y);
	/* 若所選的棋子并非自己的棋子或者目標結點已經有棋子則JudgeMove返回0,棋子不能移動 */
	if(!JudgeSellect(gamerID,start)||(Nodes[end].Chessman!=0))
		return 0;
	Nowroad=-1; 							// Nowroad的初值為-1
	if(instant<30*30)
		/* 判斷棋子是否移到附近的點由于兩鄰近結點之間的距離為27,
			所以只要instant<30*30則次二結點即為鄰近接結點 */
	{
		for(int i=0;i<121;i++)					// 搜索開始時的初始化
		{
			Nodes[i].visited=0;				// 所有標志位(visited)清零
			Nodes[i].sellect=0;				// 所有結點都未選定
		}
		Nowroad=-1;
		/* 若目標結點即為鄰近的結點則路徑數組里只用記錄節點序號start和節點序號end */
		road[++Nowroad]=start;
		road[++Nowroad]=end;
		return 1;
	}
									// 若棋子是跳走,則搜索圖,看是否
									// 存在符合規則的目標節點
	else if( DFS( start,end))    					// 若存在路徑，記錄路徑，返回1
		 {
			for( int i=0;i< 121;i ++)			// 為下一次的搜索做初始化
			{
				Nodes[i].visited=0;			// 所有標志位(visited)清零
				Nodes[i].sellect=0;			// 所有結點都未選定
			}
			return 1;
		 }
		 else							// 棋子既不能移步也不能跳走則此步不可走,返回0
		{
			for(int i=0;i< 121;i++)				// 為下一次的搜索做初始化
			{
				Nodes[i].visited=0;			// 所有標志位(visited)清零
				Nodes[i].sellect=0;			// 所有結點都未選定
			}
			return 0;
		}
}

//判斷是否已經有游戲者勝利
int _ChessBoard::Decide(int gamerID)
{
	int a[6][10]={	{0,1,2,3,4,5,6,7,8,9},
			{111,112,113,114,115,116,117,118,119,120}};
	int row=gamerID-1;  						// gamerID-1對應a數組的第row行
	if(row%2==0)       						// 如果row為偶數,則他的目標結點
		row++;							// 序號為a數組的row++行對應的序號
	else row--;							// 如果row為奇數,則他的目標結點
									// 序號為a數組的row--行對應的序號
	for(int i=0;i<10;i++)
	{								// 如果還有一個棋子未到達對面的結點上則還未勝利
			if(Nodes[a[row][i]].Chessman!=gamerID)
			return 0;
	}
	return 1;
}

_Nodes *_ChessBoard::AllNodes()						// 返回Nodes數組
{
	return Nodes;
}

int * _ChessBoard::MoveRoad()						// 返回road數組
{
	return road;
}

void _ChessBoard::record(int start,int end)				// 記錄每次走棋棋，也就是將記錄路徑的鏈表增加一位
{
	_link *p=new _link;						// 一個指向_link指針類型的指針
	p->start=start;
	p->end=end;
	p->next=NULL;
	p->before=tail;
	tail->next=p;
	tail=p;
	countstep++;							// 步驟數加一

}
void _ChessBoard::MoveIt(int start,int end)				// 移動棋子
{
	record(start,end);						// 記錄下來便于悔棋
	Nodes[end].Chessman=Nodes[road[0]].Chessman;			// end點的棋子類型和初始點的一樣
	Nodes[road[0]].Chessman=0;					// 初始點的棋子的Chessman置位0,即此處無棋子
	for(int i=0;i< 121;i++)						// 為下一次的選定重新初始化
		Nodes[i].sellect=0;
	Nowroad=-1;							// 恢復記錄路徑用到的Nowroad
}

void _ChessBoard::back()						// 悔棋時返回到上一步的狀態
{
	if(tail==NULL||countstep<2)	//若尾指針沒有指向任何節點（沒有走棋）或對方還沒有走第一步棋，不能悔棋
		return;
	for(int i=2;i>0;i--)
	{
		Nodes[tail->start].Chessman=Nodes[tail->end].Chessman;	// 恢復原先結點的棋子
		Nodes[tail->end].Chessman=0;				// 后來結點恢復無子狀態
		tail=tail->before;					// 尾指針遷移
		delete tail->next;					// 釋放最后一個指針
		countstep--;						// 步驟數減一
	}

}

_ChessBoard::~_ChessBoard()						// 析構函數釋放記錄每步棋路進的鏈表
{
	while(head!=NULL)
	{
		head=head->next;
		delete head->before;
	}
}