VC实例迷宫问题寻路鼠标关键字 VC实例 迷宫 寻路 鼠标 行列 标志一，新建一个单文档程序Ex0605。 二，增加两个类，最好放在单独的文件中，放在视图类也行，就是不规范。 以上是头文件的内容 class CMazeMap//迷宫地图类{ public :bool SearchPath();//查找路径bool IslegalRowCol(int iRow,int iCol);//行列是否合法CRect ChangeMapState(CRect r,CPoint pt);//根据范围和鼠标点击的坐标改变状态 void CopyData(const CMazeMap& other);//复制数据，不改变行列号CMazeMap(); CMazeMap(const CMazeMap& other); ~CMazeMap(); void Draw(CDC* pDC,CRect r);//绘出迷宫地图的信息void SetMapState(int iRow,int iCol,int iState);//设置某一块的状态void ChangeRowCol(int iRow ,int iCol);//改变行列数，行列数变小时，会丢部分数据int GetMapState(int iRow,int iCol){return m_pMapData[iRow][iCol];};int GetRowNum(){return m_iRowNum;};int GetColNum(){return m_iColNum;};private :void SetColNum(int iColNum);//设置列数，数据不变void SetRowNum(int iRowNum);//设置行数，数据不变void ReleaseData();//释放数据int ** CreateInitData();//new数据，并初始化int ** m_pMapData ;//数据内容,0表示不可到达，1表示可到达，2表示处于当前路径int m_iRowNum ;//行号int m_iColNum ;//列号}; class CSearchPath//寻找第一条路径算法类{ public :bool GetAStepRowCol(int iStepNO,int& iRow,int& iCol);//取得某一步的行列int GetStepNum();//取得总步数CSearchPath(CMazeMap& map); bool Search();//查找每第一条路径private :bool Back();//退回bool Move(int iType);//移动（右移下移左移上移)int m_iStep ;//当前步数，0表示起点int m_rowSet[1000] ;//存放每步的行int m_colSet[1000] ;//存放每步的列int m_iMoveType[1000];//每步的移动方式CMazeMap m_map ;//地图数据 }; 以下是源文件的内容 CMazeMap::CMazeMap() { SetRowNum(3); SetColNum(3); m_pMapData = CreateInitData(); } CMazeMap::CMazeMap(const CMazeMap& other) { m_iRowNum = other.m_iRowNum ; m_iColNum = other.m_iColNum ; m_pMapData = CreateInitData(); //复制数据，以免数据丢掉 for (int i = 0 ; i < m_iRowNum ; i++ )memcpy(m_pMapData[i],other.m_pMapData[i],sizeof(int)*m_iColNum); } CMazeMap::~CMazeMap() { ReleaseData(); } int ** CMazeMap::CreateInitData(){ int ** pMapData = new int*[m_iRowNum];if ( NULL == pMapData )return NULL ;for (int i = 0 ; i < m_iRowNum ; i++ ){ pMapData[i] = new int[m_iColNum]; memset(pMapData[i],0,sizeof(int)*m_iColNum);//置0 } return pMapData ;} void CMazeMap::ReleaseData(){ if ( NULL == m_pMapData )return ;for (int i = 0 ; i < m_iRowNum ; i++ )delete [] m_pMapData[i] ;delete [] m_pMapData ;m_pMapData = NULL; } void CMazeMap::SetRowNum(int iRowNum){ if ( iRowNum < 3 )iRowNum = 3 ;//最少行数是3 if ( iRowNum > 20 )iRowNum = 20 ;//最大20 m_iRowNum = iRowNum ; } void CMazeMap::SetColNum(int iColNum){ if ( iColNum < 3 )iColNum = 3 ;//最少行数是3 if ( iColNum > 20 )iColNum = 20 ;//最大20 m_iColNum = iColNum ; } void CMazeMap::ChangeRowCol(int iRow, int iCol){ CMazeMap tmp(*this);//备份当前数据 ReleaseData(); if ( 0 != iRow )SetRowNum(iRow); if ( 0 != iCol )SetColNum(iCol); m_pMapData = CreateInitData(); CopyData(tmp);//复制数据 } void CMazeMap::SetMapState(int iRow, int iCol,int iState){ if ( iRow < 0 || iRow >= m_iRowNum || iCol < 0 || iCol >= m_iColNum )return ;//行列号不合法if (iState < 0 || iState > 2 )return ;//状态不合法m_pMapData[iRow][iCol] = iState ; } void CMazeMap::Draw(CDC *pDC, CRect r){ CBrush brush[3] ;//建立三个刷子，对应三种不同的状态 brush[0].CreateSolidBrush(RGB(255,0,0)); brush[1].CreateSolidBrush(RGB(0,255,0)); brush[2].CreateSolidBrush(RGB(0,0,255)); CSize size(r.Width()/m_iColNum,r.Height()/m_iRowNum); for ( int i = 0 ; i < m_iRowNum ; i++ )for ( int j = 0 ; j < m_iColNum ; j++ ){ CPoint pt(r.left + size.cx * j, r.top + size.cy * i); CRect rCell(pt,size); rCell.DeflateRect(1,1,1,1);//留点空隙 int iState = m_pMapData[i][j];pDC->FillRect(&rCell,&brush[iState]); } } void CMazeMap::CopyData(const CMazeMap &other){ //取得源数据、目的数据中行列较小者，以免溢出 int iMinRow = min(m_iRowNum,other.m_iRowNum);int iMinCol = min(m_iColNum,other.m_iColNum);//复制数据，以免数据丢掉 for (int i = 0 ; i < iMinRow ; i++ )memcpy(m_pMapData[i],other.m_pMapData[i],sizeof(int)*iMinCol); } //r整个地图的范围，point鼠标点击的位置 CRect CMazeMap::ChangeMapState(CRect r, CPoint point) { //取得一个单格的大小 CSize size(r.Width()/m_iColNum,r.Height()/m_iRowNum); int iRow = point.y/size.cy ;//取得行号if ( iRow >= m_iRowNum )return CRect(0,0,0,0);//超出下边界int iCol = point.x/size.cx ;//取得列号if ( iCol >= m_iColNum )return CRect(0,0,0,0);//超出右边界int iState = GetMapState(iRow,iCol);if ( 0 == iState )iState = 1 ; else if( 1 == iState || 2 == iState )iState = 0 ; SetMapState(iRow,iCol,iState); //只刷新一部分，以免闪烁 CPoint pt(r.left + size.cx * iCol, r.top + size.cy * iRow); CRect rCell(pt,size); return rCell ;} bool CMazeMap::IslegalRowCol(int iRow, int iCol){ return (iRow >= 0 && iRow < m_iRowNum && iCol >= 0 && iCol < m_iColNum);} bool CMazeMap::SearchPath(){ //清空路径标志 for (int i = 0 ; i < m_iRowNum ; i++ )for (int j = 0 ; j < m_iColNum ; j++ ){ if ( 2 == GetMapState(i,j))SetMapState(i,j,1); } //查找路径 CSearchPath find(*this); if (!find.Search())return false ;//设置路径标志 for ( i = 0 ; i < find.GetStepNum(); i++ ){ int iRow,iCol ;find.GetAStepRowCol(i,iRow,iCol); SetMapState(iRow,iCol,2); } return true ;} CSearchPath::CSearchPath(CMazeMap& map):m_map(map) { m_iStep = 1 ; memset(m_rowSet,0,1000*sizeof(int)); memset(m_colSet,0,1000*sizeof(int)); memset(m_iMoveType,0,1000*sizeof(int)); } bool CSearchPath::Move(int iType){ m_iMoveType[m_iStep] = iType ;//无论是否移动成功都要记下来 //取得上一步的位置 int iRow = m_rowSet[m_iStep - 1] ;int iCol = m_colSet[m_iStep - 1] ;switch (iType){ case 1://右移iCol++; break ;case 2://下移iRow++; break ;case 3://左移iCol--; break ;case 4://上移iRow--; break ;default :ASSERT(false); return false; break ;} if (!m_map.IslegalRowCol(iRow,iCol))return false ;//行列号不是合法if (0 == m_map.GetMapState(iRow,iCol))return false;//此格子不是可以通过for (int i = 0 ; i < m_iStep ; i++ )if ( iCol == m_colSet[i] && iRow == m_rowSet[i])return false ;//进入死循环m_colSet[m_iStep] = iCol ; m_rowSet[m_iStep] = iRow ; return true ;} bool CSearchPath::Search(){ while (true){ int iType = m_iMoveType[m_iStep] + 1 ;if ( iType > 4 )if (!Back())return false ;else continue ;if (!Move(iType))continue ; //移动失败if (m_map.GetRowNum()-1 == m_rowSet[m_iStep] && m_map.GetColNum()-1 == m_colSet[m_iStep])return true ;//到达终点m_iStep++; } return false ;} bool CSearchPath::Back(){ if ( 1 == m_iStep )return false ;//退到起点，无路可退m_iMoveType[m_iStep] = 0 ; m_iStep-- ; return true ;} int CSearchPath::GetStepNum(){ return m_iStep+1 ;//起点第0步也算在内} bool CSearchPath::GetAStepRowCol(int iStepNO,int& iRow,int& iCol){ if ( iStepNO < 0 || iStepNO > m_iStep )return false ;iRow = m_rowSet[iStepNO]; iCol = m_colSet[iStepNO]; return true ;} 三，在视图类的头文件#include "MazeMap.h"，并为视图类定议一个对象CMazeMap m_findMap; 四，在视图类的构造函数中设置行列。 CEx0605View::CEx0605View() { m_findMap.ChangeRowCol(10,9); } 五，修改视图类的OnDraw函数。 void CEx0605View::OnDraw(CDC* pDC){ CRect r ; GetClientRect(&r); m_findMap.Draw(pDC,r); } 六，在视图类，响应鼠标左键单击消息，具体内容如下： void CEx0605View::OnLButtonDown(UINT nFlags, CPoint point){ CView::OnLButtonDown(nFlags, point); CRect r ; GetClientRect(&r); m_findMap.ChangeMapState(r,point); m_findMap.SearchPath(); Invalidate();//重新排序后，全刷新一下 // TODO: Add your message handler code here and/or call default CView::OnLButtonDown(nFlags, point); } 七，操作方法，单击鼠标左键，会改变每个小块的状态，红色表示无法通过，绿色表示可以通过，如果有路径连通左上角和右下角，此路径将以蓝色显示，单击红块会变成绿块，绿（蓝）块会变成红块。注：此路径不一定是最优路径。 注意: 直接复制需要重新排版. 一，新建一个单文档程序Ex0605。 二，增加两个类，最好放在单独的文件中，放在视图类也行，就是不规范。 以上是头文件的内容 class CMazeMap//迷宫地图类{ public :bool SearchPath();//查找路径bool IslegalRowCol(int iRow,int iCol);//行列是否合法CRect ChangeMapState(CRect r,CPoint pt);//根据范围和鼠标点击的坐标改变状态 void CopyData(const CMazeMap& other);//复制数据，不改变行列号CMazeMap(); CMazeMap(const CMazeMap& other); ~CMazeMap(); void Draw(CDC* pDC,CRect r);//绘出迷宫地图的信息void SetMapState(int iRow,int iCol,int iState);//设置某一块的状态void ChangeRowCol(int iRow ,int iCol);//改变行列数，行列数变小时，会丢部分数据int GetMapState(int iRow,int iCol){return m_pMapData[iRow][iCol];};int GetRowNum(){return m_iRowNum;};int GetColNum(){return m_iColNum;};private :void SetColNum(int iColNum);//设置列数，数据不变void SetRowNum(int iRowNum);//设置行数，数据不变void ReleaseData();//释放数据int ** CreateInitData();//new数据，并初始化int ** m_pMapData ;//数据内容,0表示不可到达，1表示可到达，2表示处于当前路径int m_iRowNum ;//行号int m_iColNum ;//列号}; class CSearchPath//寻找第一条路径算法类{ public :bool GetAStepRowCol(int iStepNO,int& iRow,int& iCol);//取得某一步的行列int GetStepNum();//取得总步数CSearchPath(CMazeMap& map); bool Search();//查找每第一条路径private :bool Back();//退回bool Move(int iType);//移动（右移下移左移上移)int m_iStep ;//当前步数，0表示起点int m_rowSet[1000] ;//存放每步的行int m_colSet[1000] ;//存放每步的列int m_iMoveType[1000];//每步的移动方式CMazeMap m_map ;//地图数据 }; 以下是源文件的内容 CMazeMap::CMazeMap() { SetRowNum(3); SetColNum(3); m_pMapData = CreateInitData(); } CMazeMap::CMazeMap(const CMazeMap& other) { m_iRowNum = other.m_iRowNum ; m_iColNum = other.m_iColNum ; m_pMapData = CreateInitData(); //复制数据，以免数据丢掉 for (int i = 0 ; i < m_iRowNum ; i++ )memcpy(m_pMapData[i],other.m_pMapData[i],sizeof(int)*m_iColNum); } CMazeMap::~CMazeMap() { ReleaseData(); } int ** CMazeMap::CreateInitData(){ int ** pMapData = new int*[m_iRowNum];if ( NULL == pMapData )return NULL ;for (int i = 0 ; i < m_iRowNum ; i++ ){ pMapData[i] = new int[m_iColNum]; memset(pMapData[i],0,sizeof(int)*m_iColNum);//置0 } return pMapData ;} void CMazeMap::ReleaseData(){ if ( NULL == m_pMapData )return ;for (int i = 0 ; i < m_iRowNum ; i++ )delete [] m_pMapData[i] ;delete [] m_pMapData ;m_pMapData = NULL; } void CMazeMap::SetRowNum(int iRowNum){ if ( iRowNum < 3 )iRowNum = 3 ;//最少行数是3 if ( iRowNum > 20 )iRowNum = 20 ;//最大20 m_iRowNum = iRowNum ; } void CMazeMap::SetColNum(int iColNum){ if ( iColNum < 3 )iColNum = 3 ;//最少行数是3 if ( iColNum > 20 )iColNum = 20 ;//最大20 m_iColNum = iColNum ; } void CMazeMap::ChangeRowCol(int iRow, int iCol){ CMazeMap tmp(*this);//备份当前数据 ReleaseData(); if ( 0 != iRow )SetRowNum(iRow); if ( 0 != iCol )SetColNum(iCol); m_pMapData = CreateInitData(); CopyData(tmp);//复制数据 } void CMazeMap::SetMapState(int iRow, int iCol,int iState){ if ( iRow < 0 || iRow >= m_iRowNum || iCol < 0 || iCol >= m_iColNum )return ;//行列号不合法if (iState < 0 || iState > 2 )return ;//状态不合法m_pMapData[iRow][iCol] = iState ; } void CMazeMap::Draw(CDC *pDC, CRect r){ CBrush brush[3] ;//建立三个刷子，对应三种不同的状态 brush[0].CreateSolidBrush(RGB(255,0,0)); brush[1].CreateSolidBrush(RGB(0,255,0)); brush[2].CreateSolidBrush(RGB(0,0,255)); CSize size(r.Width()/m_iColNum,r.Height()/m_iRowNum); for ( int i = 0 ; i < m_iRowNum ; i++ )for ( int j = 0 ; j < m_iColNum ; j++ ){ CPoint pt(r.left + size.cx * j, r.top + size.cy * i); CRect rCell(pt,size); rCell.DeflateRect(1,1,1,1);//留点空隙 int iState = m_pMapData[i][j];pDC->FillRect(&rCell,&brush[iState]); } } void CMazeMap::CopyData(const CMazeMap &other){ //取得源数据、目的数据中行列较小者，以免溢出 int iMinRow = min(m_iRowNum,other.m_iRowNum);int iMinCol = min(m_iColNum,other.m_iColNum);//复制数据，以免数据丢掉 for (int i = 0 ; i < iMinRow ; i++ )memcpy(m_pMapData[i],other.m_pMapData[i],sizeof(int)*iMinCol); } //r整个地图的范围，point鼠标点击的位置 CRect CMazeMap::ChangeMapState(CRect r, CPoint point) { //取得一个单格的大小 CSize size(r.Width()/m_iColNum,r.Height()/m_iRowNum); int iRow = point.y/size.cy ;//取得行号if ( iRow >= m_iRowNum )return CRect(0,0,0,0);//超出下边界int iCol = point.x/size.cx ;//取得列号if ( iCol >= m_iColNum )return CRect(0,0,0,0);//超出右边界int iState = GetMapState(iRow,iCol);if ( 0 == iState )iState = 1 ; else if( 1 == iState || 2 == iState )iState = 0 ; SetMapState(iRow,iCol,iState); //只刷新一部分，以免闪烁 CPoint pt(r.left + size.cx * iCol, r.top + size.cy * iRow); CRect rCell(pt,size); return rCell ;} bool CMazeMap::IslegalRowCol(int iRow, int iCol){ return (iRow >= 0 && iRow < m_iRowNum && iCol >= 0 && iCol < m_iColNum);} bool CMazeMap::SearchPath(){ //清空路径标志 for (int i = 0 ; i < m_iRowNum ; i++ )for (int j = 0 ; j < m_iColNum ; j++ ){ if ( 2 == GetMapState(i,j))SetMapState(i,j,1); } //查找路径 CSearchPath find(*this); if (!find.Search())return false ;//设置路径标志 for ( i = 0 ; i < find.GetStepNum(); i++ ){ int iRow,iCol ;find.GetAStepRowCol(i,iRow,iCol); SetMapState(iRow,iCol,2); } return true ;} CSearchPath::CSearchPath(CMazeMap& map):m_map(map) { m_iStep = 1 ; memset(m_rowSet,0,1000*sizeof(int)); memset(m_colSet,0,1000*sizeof(int)); memset(m_iMoveType,0,1000*sizeof(int)); } bool CSearchPath::Move(int iType){ m_iMoveType[m_iStep] = iType ;//无论是否移动成功都要记下来 //取得上一步的位置 int iRow = m_rowSet[m_iStep - 1] ;int iCol = m_colSet[m_iStep - 1] ;switch (iType){ case 1://右移iCol++; break ;case 2://下移iRow++; break ;case 3://左移iCol--; break ;case 4://上移iRow--; break ;default :ASSERT(false); return false; break ;} if (!m_map.IslegalRowCol(iRow,iCol))return false ;//行列号不是合法if (0 == m_map.GetMapState(iRow,iCol))return false;//此格子不是可以通过for (int i = 0 ; i < m_iStep ; i++ )if ( iCol == m_colSet[i] && iRow == m_rowSet[i])return false ;//进入死循环m_colSet[m_iStep] = iCol ; m_rowSet[m_iStep] = iRow ; return true ;} bool CSearchPath::Search(){ while (true){ int iType = m_iMoveType[m_iStep] + 1 ;if ( iType > 4 )if (!Back())return false ;else continue ;if (!Move(iType))continue ; //移动失败if (m_map.GetRowNum()-1 == m_rowSet[m_iStep] && m_map.GetColNum()-1 == m_colSet[m_iStep])return true ;//到达终点m_iStep++; } return false ;} bool CSearchPath::Back(){ if ( 1 == m_iStep )return false ;//退到起点，无路可退m_iMoveType[m_iStep] = 0 ; m_iStep-- ; return true ;} int CSearchPath::GetStepNum(){ return m_iStep+1 ;//起点第0步也算在内} bool CSearchPath::GetAStepRowCol(int iStepNO,int& iRow,int& iCol){ if ( iStepNO < 0 || iStepNO > m_iStep )return false ;iRow = m_rowSet[iStepNO]; iCol = m_colSet[iStepNO]; return true ;} 三，在视图类的头文件#include "MazeMap.h"，并为视图类定议一个对象CMazeMap m_findMap; 四，在视图类的构造函数中设置行列。 CEx0605View::CEx0605View() { m_findMap.ChangeRowCol(10,9); } 五，修改视图类的OnDraw函数。 void CEx0605View::OnDraw(CDC* pDC){ CRect r ; GetClientRect(&r); m_findMap.Draw(pDC,r); } 六，在视图类，响应鼠标左键单击消息，具体内容如下： void CEx0605View::OnLButtonDown(UINT nFlags, CPoint point){ CView::OnLButtonDown(nFlags, point); CRect r ; GetClientRect(&r); m_findMap.ChangeMapState(r,point); m_findMap.SearchPath(); Invalidate();//重新排序后，全刷新一下 // TODO: Add your message handler code here and/or call default CView::OnLButtonDown(nFlags, point); } 七，操作方法，单击鼠标左键，会改变每个小块的状态，红色表示无法通过，绿色表示可以通过，如果有路径连通左上角和右下角，此路径将以蓝色显示，单击红块会变成绿块，绿（蓝）块会变成红块。注：此路径不一定是最优路径。 注意: 直接复制需要重新排版.
|
|||