www.gusucode.com > 马走日棋盘搜索算法C++源码程序 > 马走日棋盘搜索算法/ChessDisplay/ChessDisplay/ChessCalculator.cpp
//########################################################################### //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 //########################################################################### //功能 : // 设置默认的搜索环境 //########################################################################### 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; }; //########################################################################### //功能 : // 释放搜索环境中动态分配的空间 //########################################################################### CChessCalculator::~CChessCalculator() { if( m_start ) { for( int i = 0 ; i < m_height ; i++ ) delete[] m_chessTable[i]; delete m_chessTable; delete m_recordTable; } } //########################################################################### //功能 : // 设置搜索的起始位置 //参数 : // locOnX : 在高度上的位置 // locOnY : 在宽度上的位置 //########################################################################### void CChessCalculator::SetStartLocation( int locOnX , int locOnY )//设置棋子的起始位置; { m_curLoc.x = locOnX; m_curLoc.y = locOnY; } //########################################################################### //功能 : // 设置棋盘的大小 //参数 : // width : 棋盘宽度 // height : 棋盘高度 //########################################################################### void CChessCalculator::SetSize( int width , int height )//设置棋盘的大小; { m_width = width ; m_height = height; } //########################################################################### //功能 : // 初始化搜索环境, 启动搜索过程 //########################################################################### 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; //创建目标文档文件; if( !recordFile.Open( fileName , CFile::modeWrite , &e ) ) { AfxMessageBox( "建立目标文档文件失败!"); 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(); } //########################################################################### //功能 : // 从指定的起始位置开始搜索 //参数 : // curLoc : 当前搜索的起始位置 //返回值: // true : 搜索成功 // false : 搜索失败 //########################################################################### bool CChessCalculator::Search( Location curLoc )//开始计算; { m_complex++; //修改棋盘标志; m_chessTable[curLoc.x-1][curLoc.y-1] = 1; //是否搜索成功结束标志; if( isSuccess() ) return true; //还有未走到的棋盘点,从当前位置开始搜索; else { //递归搜索未走过的棋盘点; 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; } } } } //搜索失败,恢复棋盘标志; m_chessTable[curLoc.x-1][curLoc.y-1] = 0; return false; } //########################################################################### //功能 : // 取得当前棋盘的宽度 //返回值: // 棋盘宽度 //########################################################################### int CChessCalculator::GetWidth()//取得棋盘的宽度; { return m_width; } //########################################################################### //功能 : // 取得当前棋盘的高度 //返回值: // 棋盘高度 //########################################################################### int CChessCalculator::GetHeight()//取得棋盘的高度; { return m_height; } //########################################################################### //功能 : // 在走子记录表中查找是否包含指定的位置 //参数 : // loc : 指定要查找的位置 // n : 当前走子记录表的大小 //返回值: // true : 指定位置已经在走子记录表中 // 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; } //########################################################################### //功能: // 填写指定的当前位置和新位置到走子记录表中 //参数: // newLoc : 新位置 // curLoc : 当前位置 //########################################################################### 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; } //########################################################################### //功能 : // 判断当前位置是否合法 //返回值: // 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; } //########################################################################### //功能 : // 取得从当前位置出发可以到达的下一个新位置 //参数 : // curLoc | 当前位置 // i | 方向(0-7) //返回值: // 从当前位置的指定方向出发可以到达的新位置 //########################################################################### 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; } //########################################################################### //功能: // 图形化显示搜索结果 //参数: // CDC* | 绘图环境 //########################################################################### 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); } } //########################################################################### //功能 : // 取得当前的搜索状态 // | WAITING | WORKING | SUCCESS | FAILED // | 等待开始搜索 | 正在搜索 | 搜索成功 | 搜索失败 // //返回值: // 当前搜索状态 //########################################################################### 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; } //########################################################################### //功能 : // 取得当前已经搜索的解空间大小 //返回值: // 搜索解空间大小 //########################################################################### int CChessCalculator::GetSearchSpace() { return m_complex; } //########################################################################### //功能: // 设置显示结果模式 //参数: // delay = true : 动画显示 // delay = false : 直接显示 //########################################################################### void CChessCalculator::SetShowDelay(bool delay) { m_showDelay = delay; }