GrowRegiony[nEnd] = yy;	
		   		// 同時也表明該象素處理過
				p_bw[yy*624+xx] = 255;
				if(color[l]==1)
					dc.SetPixel(xx+11,512+10-yy,RGB(255,0,0));
				else if(color[l]==2)
					dc.SetPixel(xx+11,512+10-yy,RGB(0,255,0));
				else if(color[l]==3)
					dc.SetPixel(xx+11,512+10-yy,RGB(0,0,255));
				else
					dc.SetPixel(xx+11,512+10-yy,RGB(255,0,255));
   			}
		}
		nStart++;
	}

	delete []GrowRegionx;
	delete []GrowRegiony;
    GrowRegionx = NULL ;
	GrowRegiony = NULL ;// 釋放內存*/
}

void CMyDlg::MultipleRegionGrow(BYTE *bwImage)
{

	static int nDx[]={-1,0,1,0};
	static int nDy[]={ 0,1,0,-1};

	// 定義堆棧的起點和終點
	// 當nStart=nEnd, 表示堆棧中只有一個點
	long int nStart=0 ;
	long int nEnd=0   ;
//	p_bw=new BYTE(512*624);

	int *GrowRegionx = new int [512*624];
	int *GrowRegiony = new int [512*624];

	// 當前正在處理的象素
	int nCurrx ;
	int nCurry ;

	// 循環控制變量
	int k ;

	// 圖象的橫縱坐標,用來對當前象素的4鄰域進行遍歷
	int xx;
	int yy;

	CClientDC dc(this);

	memset(p_bw,0,sizeof(BYTE)*319488);	
	nStart=0;
	nEnd=0;
//	Sleep(1000);
	// 把種子點的坐標壓入棧
	for(int i=0;i<32;i++)
	{
		GrowRegionx[nEnd] = center_y[i]+color[i]*1000;		//千位數表示顏色
		GrowRegiony[nEnd] = center_x[i];
		nEnd++;
	}
	nEnd--;

	while (nStart<=nEnd)
	{
		// 當前種子點的坐標
		nCurrx = GrowRegionx[nStart];
		nCurry = GrowRegiony[nStart];
//		Sleep(1);

		// 對當前點的4鄰域進行遍歷
		for (k=0; k<4; k++)	
		{	
			// 4鄰域象素的坐標
			xx = nCurrx+nDx[k];
			yy = nCurry+nDy[k];
			
			// 判斷象素(xx，yy) 是否在圖像內部
			if (	((xx%1000) < 624) && ((xx%1000)>=0) && (yy<512) && (yy>=0) 
					 &&p_bw[yy*624+(xx%1000)]==0
					 &&bwImage[yy*624+(xx%1000)]==255)
			{
				// 堆棧的尾部指針后移一位
				nEnd++;

				// 象素(xx，yy) 壓入棧
				GrowRegionx[nEnd] = xx;
				GrowRegiony[nEnd] = yy;
		   		// 同時也表明該象素處理過
				p_bw[yy*624+(xx%1000)] = 255;
				if((xx/1000)==1)
					dc.SetPixel((xx%1000)+11,512+10-yy,RGB(255,0,0));
				else if((xx/1000)==2)
					dc.SetPixel((xx%1000)+11,512+10-yy,RGB(0,255,0));
				else if((xx/1000)==3)
					dc.SetPixel((xx%1000)+11,512+10-yy,RGB(0,0,255));
				else
					dc.SetPixel((xx%1000)+11,512+10-yy,RGB(255,0,255));
   			}
		}
		nStart++;
	}

	delete []GrowRegionx;
	delete []GrowRegiony;
    GrowRegionx = NULL ;
	GrowRegiony = NULL ;// 釋放內存*/
}

void CMyDlg::NormalBacktrackingSearch()
{
	int i,k=0;
	CString tempstring;
	for(i=0;i<32;i++)	//初始化
		color[i]=0;

	while(k<32)
	{
		color[k]++;

		for(i=0;i<k;i++)
		{
			if(color[i]==color[k]&&NeighbourMatrix[i][k]==1)
			{
				color[k]++;
				i=0;		//從頭重新檢索
			}
			if(color[k]>=5)
			{
				tempstring.Format("%s",province[k]);
				info+="在";
				info+=tempstring;
				info+="處發生了回溯！";
				info+="\r\n";		
				ShowWindow();
				info.Empty();

				color[k]=0;
				k--;
				k--;
				break;		//跳出內層循環，回溯到上一層
			}
		}
		RegionGrow(*bmpTwo,k);
		k++;
	}
	MessageBox("Mission Complete!");
//	for(i=0;i<32;i++)
//		fout<<color[i]<<endl;
}

void CMyDlg::HeuristicBacktrackingSearch()
{
	bool JudgeMatrix[32][4]={0};	//32個變量的值域
	int Number[32]={0};		//可行值的個數
	int i,j,k=1;
	int ConstraintNumber[32]={0};		//跟該變量有關的約束個數
	int FirstVariable=0;
	bool Flag[32]={0};		//標識該變量是否已經賦過值
	int temp_max=0,temp_min=0,temp=0,temp_number[4]={0},temp2=0;

	CString tempstring;

	for(i=0;i<32;i++)		//初始化
		Number[i]=4;
	for(i=0;i<32;i++)
		for(j=0;j<4;j++)
			JudgeMatrix[i][j]=true;
	
	for(i=0;i<32;i++)			//度啟發式，選擇涉及約束條件最多的變量先賦值顏色1；
	{
		for(j=0;j<32;j++)
			if(NeighbourMatrix[i][j]==1)
				ConstraintNumber[i]++;
	}

	for(i=0;i<32;i++)
	{
		if(ConstraintNumber[i]>temp_max)
		{
			temp_max=ConstraintNumber[i];
			FirstVariable=i;
		}
	}

	color[FirstVariable]=1;
	info+="由度啟發式，第一個要賦值的變量是";
	tempstring.Format("%s",province[FirstVariable]);
	info+=tempstring;
	info+="。\r\n";
	ShowWindow();

	RegionGrow(*bmpTwo,FirstVariable);
	Sleep(1000);
	fout<<FirstVariable<<"  "<<"1"<<endl;

	Flag[FirstVariable]=true;

	for(i=0;i<32;i++)		//前向檢驗
	{
		if(NeighbourMatrix[FirstVariable][i]==1)
		{
			JudgeMatrix[i][0]=false;
			Number[i]--;
		}
	}

	while(k<32)
	{
		temp_min=5;
		for(i=0;i<32;i++)		//最少剩余值啟發式
		{
			if(Number[i]<temp_min&&!Flag[i])
			{
				temp_min=Number[i];
				temp=i;
			}
		}
		Flag[temp]=true;
		info+="由最少剩余值啟發式，下一個要賦值的變量是  ";
		tempstring.Format("%s",province[temp]);
		info+=tempstring;
		info+="  。";
		ShowWindow();

		for(i=0;i<4;i++)
			temp_number[i]=0;
		for(i=0;i<4;i++)		//最少約束值啟發式，temp_number[i]表示第i個顏色影響到的剩余變量數
		{
			if(JudgeMatrix[temp][i]==false)
				temp_number[i]=100;
			else
			{
				for(j=0;j<32&&!Flag[j];j++)
					if(NeighbourMatrix[temp][j]==1&&JudgeMatrix[j][i]==true)
						temp_number[i]++;
			}
		}
		temp_min=100;
		temp2=0;
		for(i=0;i<4;i++)
		{
			if(temp_number[i]<temp_min)
			{
				temp_min=temp_number[i];
				temp2=i;
			}
		}
		color[temp]=temp2+1;

		info+="根據最少約束值啟發式，為其著的顏色為  ";
		tempstring.Format("%s",colorname[temp2]);
		info+=tempstring;
		info+="  。\r\n\r\n";
		ShowWindow();
		Sleep(500);
		RegionGrow(*bmpTwo,temp);
		Sleep(1000);
//		fout<<temp<<"  "<<temp2+1<<endl;

		for(i=0;i<32;i++)		//前向檢驗
		{
			if(NeighbourMatrix[temp][i]==1&&!Flag[i])
			{
				JudgeMatrix[i][temp2]=false;
				Number[i]--;
			}
		}
		k++;
	}
	info.Empty();
	MessageBox("Mission Complete!");
}


void CMyDlg::GA()
{
	int SIZE;
	double CrossProbability,MutateProbability;
	long GENERATION;

	UpdateData(true);
	SIZE=m_size;
	CrossProbability=m_CrossProbability;
	MutateProbability=m_MutateProbability;
	GENERATION=m_GENERATION;

	int lable=0;	//臨時存放的數組標識

	int i,j,k,l;
	double sum=0,sum1=0,sum2=0;
	double temp=0;
	int temp2=0;
	int num1,num2;

//	int allmatrix[SIZE][32]={0};
	int **allmatrix;
	allmatrix=new int *[SIZE];

	for(i=0;i<SIZE;i++)
	{
		allmatrix[i]=new int[32];
	}

//	int allmatrix_temp[SIZE][32]={0};	//臨時存放的數組
	int **allmatrix_temp;
	allmatrix_temp=new int *[SIZE];

	for(i=0;i<SIZE;i++)
	{
		allmatrix_temp[i]=new int[32];
	}

//	double fitness[SIZE]={0};			//適應性度量
	double *fitness;					//錄入B數組
	fitness=new double[SIZE];
	
	double best_fitness;		//顯示用
	int best_number;

	CString tempstring;

	srand((unsigned)time(NULL));
	for(i=0;i<SIZE;i++)			//種群初始化
	{
		for(j=0;j<32;j++)
		{
			allmatrix[i][j]=int(4*double(rand())/(RAND_MAX+1));
//			fout<<allmatrix[i][j];
		}
//		fout<<endl;
	}

	for(l=0;l<=GENERATION;l++)
	{
		sum=0;
		sum1=0;
		sum2=0;
		
//		fout<<"第"<<l<<"代中："<<endl;
		for(i=0,fitness[i]=1;i<SIZE;i++,fitness[i]=1)				//計算適應度
		{
			for(j=0;j<32;j++)
				for(k=j+1;k<32;k++)
					if(NeighbourMatrix[j][k]==1&&allmatrix[i][j]==allmatrix[i][k])
						fitness[i]++;
//			fout<<fitness[i]<<"   ";
		}
//		fout<<endl;

		for(i=0;i<SIZE;i++)
			fitness[i]=1/fitness[i];

		best_fitness=fitness[0];
		best_number=0;
		for(i=1;i<SIZE;i++)
		{
			if(fitness[i]>best_fitness)
			{
				best_fitness=fitness[i];
				best_number=i;
			}
		}

		if(l%20==0)
		{
			tempstring.Format("%d",l);
			info+="第";
			info+=tempstring;
			info+="代中，最佳適應值為：";
			tempstring.Format("%f",best_fitness);
			info+=tempstring;
			info+="\r\n";
			ShowWindow();
		}

		if(best_fitness==1)
		{
			for(i=0;i<32;i++)
			{
				color[i]=allmatrix[best_number][i]+1;
//				RegionGrow(*bmpTwo,i);
//				fout<<color[i]<<"  ";
			}
			tempstring.Format("%d",l);
			info+="第";
			info+=tempstring;
			info+="代中，最佳適應值為：";
			tempstring.Format("%f",best_fitness);
			info+=tempstring;
			info+="\r\n";
			ShowWindow();
			info.Empty();

			MultipleRegionGrow(*bmpTwo);
			l=GENERATION+2;				//跳出循環
			MessageBox("Mission Complete!");
			break;
		}

		for(i=0;i<SIZE;i++)
			sum+=fitness[i];

		for(lable=0;lable<SIZE;lable=lable+2)		//一次完整的選擇雜交過程
		{			
			temp=double(rand())/RAND_MAX;
			i=0;
			sum1=fitness[0];
			while(double(sum1/sum)<temp)	//輪轉法選擇交叉的母代num1
			{
				i++;
				sum1+=fitness[i];
			}
			num1=i;

			temp=double(rand())/RAND_MAX;
			i=0;
			sum2=fitness[0];
			while(double(sum2/sum)<temp)	//輪轉法選擇交叉的母代num2
			{
				i++;
				sum2+=fitness[i];
			}
			num2=i;

			temp2=int(32*double(rand())/(RAND_MAX+1));	//交叉的位置

//	fout<<"num1="<<num1<<"  num2="<<num2<<"  temp2="<<temp2<<endl;

			if(double(rand())/RAND_MAX<CrossProbability)	//是否交叉
			{
				for(i=0;i<temp2;i++)
				{
					allmatrix_temp[lable][i]=allmatrix[num1][i];
					allmatrix_temp[lable+1][i]=allmatrix[num2][i];
				}	
				for(i=temp2;i<32;i++)
				{
					allmatrix_temp[lable][i]=allmatrix[num2][i];
					allmatrix_temp[lable+1][i]=allmatrix[num1][i];
				}
			}
			else
			{
				for(i=0;i<32;i++)
				{
					allmatrix_temp[lable][i]=allmatrix[num1][i];
					allmatrix_temp[lable+1][i]=allmatrix[num2][i];
				}
			}
		}
		
		for(i=0;i<SIZE;i++)
		{
			if(double(rand())/RAND_MAX<MutateProbability)
			{
				temp2=int(32*double(rand())/(RAND_MAX+1));	//變異的位置
				allmatrix_temp[i][temp2]=int(4*double(rand())/(RAND_MAX+1));
			}
		}

		for(i=0;i<SIZE;i++)
		{
			for(j=0;j<32;j++)
			{
				allmatrix[i][j]=allmatrix_temp[i][j];
//		fout<<allmatrix[i][j];
			}
//	fout<<endl;
		}
	}

	if(l==GENERATION+1)
	{
		info+="無解！\r\n";
		ShowWindow();
		info.Empty();
	}
}


void CMyDlg::OnButton1() 
{
	// TODO: Add your control notification handler code here
	ShowWindow();
	Open();
	Thining();
	NormalBacktrackingSearch();
}

void CMyDlg::OnButton2() 
{
	// TODO: Add your control notification handler code here
	ShowWindow();
	Open();
	Thining();
	HeuristicBacktrackingSearch();
}

void CMyDlg::OnButton3() 
{
	// TODO: Add your control notification handler code here
	ShowWindow();
	Open();
	Thining();
	GA();
}

void CMyDlg::ShowWindow()
{
	CEdit*HInfo=(CEdit*)GetDlgItem(IDC_EDIT1);
	HInfo->SetWindowText(info);
	HInfo->LineScroll(HInfo->GetLineCount());
}

inline void CMyDlg::memError()
{
	MessageBox("Memory allocation error!");
	exit(1);
}