//###########################################################################
//ChessCalculator.cpp: implementation of the CChessCalculator class.
//###########################################################################
#include "stdafx.h"
#include "ChessDisplay.h"
#include "ChessCalculator.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//###########################################################################
//功能  :
//          設(shè)置默認(rèn)的搜索環(huán)境
//###########################################################################
CChessCalculator::CChessCalculator()
{
	m_curLoc.x = 3 ; 
	m_curLoc.y = 3 ;
	m_width    = 5;
	m_height   = 5;
	m_index    = 0;
	m_complex  = 0;

	m_start    = false;
	m_result   = false;
	m_end      = false;
	m_nextTime = false;
	m_showDelay= false;
};
//###########################################################################
//功能  :
//          釋放搜索環(huán)境中動態(tài)分配的空間
//###########################################################################
CChessCalculator::~CChessCalculator()
{
	if( m_start )
	{
		for( int i = 0 ; i < m_height ; i++ )
			delete[] m_chessTable[i];
		delete m_chessTable;
		delete m_recordTable;
	}
}
//###########################################################################
//功能  :
//          設(shè)置搜索的起始位置
//參數(shù)  :   
//          locOnX    :   在高度上的位置
//          locOnY    :   在寬度上的位置
//###########################################################################
void CChessCalculator::SetStartLocation( int locOnX , int locOnY )//設(shè)置棋子的起始位置;
{ 
	m_curLoc.x = locOnX;
	m_curLoc.y = locOnY;
}
//###########################################################################
//功能  :
//          設(shè)置棋盤的大小
//參數(shù)  :
//          width   :   棋盤寬度
//          height  :   棋盤高度
//###########################################################################
void CChessCalculator::SetSize( int width , int height )//設(shè)置棋盤的大小;
{
	m_width  = width ; 
	m_height = height;
}
//###########################################################################
//功能  :
//          初始化搜索環(huán)境, 啟動搜索過程
//###########################################################################
void  CChessCalculator::StartSearch()
{
	m_index    = 0;
	m_complex  = 0;

	m_start    = false;
	m_result   = false;
	m_end      = false;
	m_showDelay= false;
	
	if( m_nextTime )
	{
		for( int i = 0 ; i < m_saveHeight ; i++ )
			delete[] m_chessTable[i];
		delete m_chessTable;

		delete[] m_recordTable;
	}

	m_nextTime = true;
	m_saveWidth = m_width;
	m_saveHeight= m_height;

	//初始化棋盤表;
	m_chessTable = new int*[m_height];
	for( int i = 0 ; i < m_height ; i++ )
	{
		m_chessTable[ i ] = new int[m_width];
		for( int j = 0 ; j < m_width ; j++ )
			m_chessTable[i][j] = 0;
	}
	
	//初始化走棋記錄表;
	m_recordTable = new Location[m_width * m_height];
	for( i = 0 ; i < m_width* m_height ; i++ )
	{
		m_recordTable[i].x = 0;
		m_recordTable[i].y = 0;
	}
	
	//記錄表記錄位置;
	m_index  = 0;
	m_start  = true;
	m_result = Search( m_curLoc );
	m_end    = true;

	//寫入文件;
	CFile  recordFile;
	CString fileName = _T("C://Record.txt");

	CFileException e;

	//創(chuàng)建目標(biāo)文檔文件;
	if( !recordFile.Open( fileName , CFile::modeWrite , &e ) )
	{
		AfxMessageBox( "建立目標(biāo)文檔文件失敗!");
		return;
	}

	char ctrl = 0x0D;
	char line = 0x0A;
	recordFile.Write( "==============================" , 30 ); 
	recordFile.Write( &ctrl , 1 ); 
	recordFile.Write( &line , 1 );

	int k = 0;
	for( i = m_width*m_height - 1 ; i >= 0 ; i-- )
	{
		char ch[20];
		
		itoa( m_recordTable[ i ].x , ch , 10 );
		recordFile.Write( (CString)ch, 1 );
		
		itoa( m_recordTable[ i ].y , ch , 10 );
		recordFile.Write( (CString)ch, 1 );

		recordFile.Write( " " , 1 );

		if( (++k)%m_width == 0 )
		{
			recordFile.Write( &ctrl , 1 ); 
			recordFile.Write( &line , 1 );
		}
	}
		
	recordFile.Close();	
}
//###########################################################################
//功能  :
//          從指定的起始位置開始搜索
//參數(shù)  :
//          curLoc   :   當(dāng)前搜索的起始位置
//返回值:
//          true     :   搜索成功
//          false    :   搜索失敗
//###########################################################################
bool  CChessCalculator::Search( Location curLoc )//開始計算;
{
	m_complex++;
	
	//修改棋盤標(biāo)志;
	m_chessTable[curLoc.x-1][curLoc.y-1] = 1;
	
	//是否搜索成功結(jié)束標(biāo)志;
	if( isSuccess() )
		return true;
	
	//還有未走到的棋盤點(diǎn),從當(dāng)前位置開始搜索;
	else
	{
		//遞歸搜索未走過的棋盤點(diǎn);
		for( int i = 0 ; i < 8 ; i++ )
		{
			Location newLocation = GetSubTreeNode( curLoc , i ) ;
			if( isValide( newLocation ) && m_chessTable[newLocation.x-1][newLocation.y-1] == 0 )
			{		
				if( Search( newLocation ) == true )
				{
					//填寫記錄表;
					MarkInTable( newLocation, curLoc );
					return true;
				}
			}	
		}
	}
	//搜索失敗,恢復(fù)棋盤標(biāo)志;
	m_chessTable[curLoc.x-1][curLoc.y-1] = 0;
	return false;
}
//###########################################################################
//功能  :
//          取得當(dāng)前棋盤的寬度
//返回值:
//          棋盤寬度
//###########################################################################
int  CChessCalculator::GetWidth()//取得棋盤的寬度;
{
	return m_width;
}
//###########################################################################
//功能  :
//          取得當(dāng)前棋盤的高度
//返回值:
//          棋盤高度
//###########################################################################
int  CChessCalculator::GetHeight()//取得棋盤的高度;
{ 
	return m_height;
}

//###########################################################################
//功能  :
//          在走子記錄表中查找是否包含指定的位置
//參數(shù)  :
//          loc    :  指定要查找的位置
//          n      :  當(dāng)前走子記錄表的大小
//返回值:
//          true   :  指定位置已經(jīng)在走子記錄表中
//          false  :  指定位置不包含在走子記錄表中
//###########################################################################
bool CChessCalculator::FindInTable( Location loc , int n )
{
	for( int i = 0 ; i < n ; i ++ )
	{
		if( loc.x == m_recordTable[i].x && loc.y == m_recordTable[i].y )
			return true;
	}
	return false;	
}
//###########################################################################
//功能:
//       填寫指定的當(dāng)前位置和新位置到走子記錄表中
//參數(shù):
//       newLoc   :   新位置
//       curLoc   :   當(dāng)前位置
//###########################################################################
void CChessCalculator::MarkInTable( Location newLoc , Location curLoc )
{
	if( FindInTable( newLoc , m_index ) == false )
		m_recordTable[m_index++] = newLoc;	
	
	if( FindInTable( curLoc , m_index ) == false )
		m_recordTable[m_index++] = curLoc;
}
//###########################################################################
//功能  :
//          判斷當(dāng)前位置是否合法
//返回值:  
//          true  :  位置合法
//          false :  位置不合法
//###########################################################################
bool CChessCalculator::isValide( Location& loc )
{
	if( loc.x >= 1 && loc.x <= m_width && loc.y >= 1 && loc.y <= m_height )
		return true;
	else
		return false;
}
//###########################################################################
//功能  :
//        判斷搜索是否成功
//返回值:
//        true  : 搜索成功
//        false : 搜索未完成
//###########################################################################
bool CChessCalculator::isSuccess()
{
	for( int i = 0 ; i < m_height ; i++ )
		for( int j = 0 ; j < m_width ; j++ )
			if( m_chessTable[i][j] == 0 )
				return false;
	return true;
}
//###########################################################################
//功能  :      
//            取得從當(dāng)前位置出發(fā)可以到達(dá)的下一個新位置
//參數(shù)  :     
//            curLoc  |   當(dāng)前位置       
//             i      |   方向(0-7)
//返回值:      
//            從當(dāng)前位置的指定方向出發(fā)可以到達(dá)的新位置
//###########################################################################
Location CChessCalculator::GetSubTreeNode( Location curLoc , int i )
{
	Location newLoc;
	switch( i )
	{
	case 0:
		newLoc.x = curLoc.x + 1;
		newLoc.y = curLoc.y + 2;
		break;
	case 1:
		newLoc.x = curLoc.x + 1;
		newLoc.y = curLoc.y - 2;
		break;

	case 2:
		newLoc.x = curLoc.x - 1;
		newLoc.y = curLoc.y + 2;
		break;

	case 3:
		newLoc.x = curLoc.x - 1;
		newLoc.y = curLoc.y - 2;
		break;

	case 4:
		newLoc.x = curLoc.x + 2;
		newLoc.y = curLoc.y + 1;
		break;

	case 5:
		newLoc.x = curLoc.x + 2;
		newLoc.y = curLoc.y - 1;
		break;

	case 6:
		newLoc.x = curLoc.x - 2;
		newLoc.y = curLoc.y + 1;
		break;

	case 7:
		newLoc.x = curLoc.x - 2;
		newLoc.y = curLoc.y - 1;
		break;

	default:
		//errors, it will never go to here;
		break;
	}
	return newLoc;
	
}
//###########################################################################
//功能:
//       圖形化顯示搜索結(jié)果
//參數(shù):
//       CDC*   |   繪圖環(huán)境
//###########################################################################
void CChessCalculator::DisplayResult( CDC* pDC )
{
	CPen   newPen;
	CPen*  oldPen;
	
	newPen.CreatePen( PS_SOLID , 2 , RGB( 225 , 225 , 225 ) );
	oldPen = pDC->SelectObject( &newPen );
	
	int indexOnX = 60;
	int indexOnY = 60;
	
	CPoint startPoint;
	CPoint endPoint;
	CPoint ChessTableStartLocation(60,60);
	
	startPoint  = ChessTableStartLocation;
	
	endPoint    = ChessTableStartLocation;
	endPoint.x += ( m_width - 1 )*indexOnX ;

	pDC->SetBkMode( TRANSPARENT  );
	
	//繪制棋盤；
	for( int i = 0 ; i < m_height ; i++ )
	{
		endPoint.y = ChessTableStartLocation.y + i*indexOnY;
		startPoint.y = ChessTableStartLocation.y + i*indexOnY;
		
		pDC->MoveTo( startPoint );
		pDC->LineTo( endPoint );
		
		char str[10];
		itoa( i+1 , str , 10 );
		pDC->TextOut( startPoint.x - 40 , startPoint.y - 3 , (CString)str );
	}
	
	startPoint  = ChessTableStartLocation;
	endPoint    = ChessTableStartLocation;
	endPoint.y += (m_height-1)*indexOnY ;
	
	for( int j = 0 ; j < m_width ; j++ )
	{
		endPoint.x = ChessTableStartLocation.x + j*indexOnX;
		startPoint.x = ChessTableStartLocation.x + j*indexOnX;
		
		pDC->MoveTo( startPoint );
		pDC->LineTo( endPoint );	
		
		char str[10];
		itoa( j+1 , str , 10 );
		pDC->TextOut( startPoint.x -3 , startPoint.y - 40 , (CString)str );
	}

	CPoint chessPosition ;
	//繪制棋子走子過程；
	int k = 0;
	for( i = m_width*m_height - 1 ; i >= 0  ; i-- )
	{
		chessPosition.x = ChessTableStartLocation.y + (m_recordTable[i].y - 1)*indexOnX;
		chessPosition.y = ChessTableStartLocation.x + (m_recordTable[i].x - 1)*indexOnY;
		
		CRect rect;
		rect.top = chessPosition.y - 20;
		rect.bottom = chessPosition.y + 20;
		rect.left = chessPosition.x - 20;
		rect.right = chessPosition.x + 20;
		pDC->Ellipse( rect );
		
		char str[10];
		itoa( k+1 , str , 10 );
		rect.top += 10;
		pDC->DrawText( (CString)str , rect , 1 );
		
		k++;
		if( m_showDelay == true )
	    	Sleep(900);
	}

}
//###########################################################################
//功能  :
//     取得當(dāng)前的搜索狀態(tài) 
//     |   WAITING     |   WORKING  |  SUCCESS   |  FAILED
//     |  等待開始搜索 |   正在搜索 |  搜索成功  |  搜索失敗
//
//返回值:
//     當(dāng)前搜索狀態(tài)
//###########################################################################
Status CChessCalculator::GetCalculateResult()
{
	if( !m_start )
		return WAITING;	

	else if( m_start && !m_end )
		return WORKING;

	else if( m_result == true )
		return SUCCESS;

	else if( m_end && !m_result )
		return FAILED;
}
//###########################################################################
//功能  :
//         取得當(dāng)前已經(jīng)搜索的解空間大小
//返回值: 
//         搜索解空間大小 
//###########################################################################
int CChessCalculator::GetSearchSpace()
{
	return m_complex;
}
//###########################################################################
//功能:
//       設(shè)置顯示結(jié)果模式
//參數(shù):
//       delay = true  :  動畫顯示 
//       delay = false :  直接顯示 
//###########################################################################
void CChessCalculator::SetShowDelay(bool delay)
{
	m_showDelay = delay; 

}