主题内容： 有个游戏玩法很类似孔明棋.
其游戏的原始规则如下:
原始棋盘为这样:
假设0为空格 1为棋子
0000000
0000000
0000000
0000000
1111111
1111111
1111111
1111111
1.棋子的移动必须经由跳过其隔壁(可以是水平或是垂直,但不能走斜角)的一颗棋到空格
2.被跳过的那颗棋子就会从棋盘上消失不见
3.只要其中一颗棋子跳到了棋盘底端,游戏就结束
但是这个程式并不要是写出来让使用者来玩
而是要使用者指定出一个空格来做为目的地(这个空格可以是原始棋盘上的任一个空格)
然后接著这个程式会自己去找出从原始棋盘走到被指定的目的地那步棋的最短移动路径
接著就把每一步棋都印出来
假设目的地被指定为X:
0000000
0000X00
0000000
0000000
1111111
1111111
1111111
1111111
移动第一步可能为以下七种之一:
1.1 1.2 1.3 1.4 1.5 1.6 1.7
0000000 0000000 0000000 0000000 0000000 0000000 0000000
0000X00 0000X00 0000X00 0000X00 0000X00 0000X00 0000X00
0000000 0000000 0000000 0000000 0000000 0000000 0000000
移动到这> 1000000 0100000 0010000 0001000 0000100 0000010 0000001
跳过的被吃掉> 0111111 1011111 1101111 1110111 1111011 1111101 1111110
从这移动> 0111111 1011111 1101111 1110111 1111011 1111101 1111110
1111111 1111111 1111111 1111111 1111111 1111111 1111111
1111111 1111111 1111111 1111111 1111111 1111111 1111111
假设第一步为1.1, 第二步可能为以下八种之一:
2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8
0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000
0000X00 0000X00 0000X00 0000X00 0000X00 0000X00 0000X00 0000X00
0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000
1100000 1010000 1001000 1000100 1000010 1000001 1000000 1000000
0011111 0101111 0110111 0111011 0111101 0111110 1001111 0111111
0011111 0101111 0110111 0111011 0111101 0111110 0111111 1001111
1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111
1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111
但是第一步也可能为1.2, 1.3, 1.4, 1.5, 1.6 及 1.7 之一
而每个第一步又能各产生出八个第二步
每个第二步又可以产生出一样数量的第三步, 以此类推直到到达目的地 X
所以可能会有非常多种可能来走到目的地
这个程式被要求如下:
1.使用者可以指定目的地(若所指定的目的地是不合法的,程式必须提出警告)
2.必须要存有所有的可能走法(可能会有非常多个阵列)
3.如果棋盘中的可能走法有重覆,只要保有一个就好(不能有重覆的)
4.必须把最早到达目的地的那步棋的所有路径给印出来
有其中一种方式的流程提示如下:
首先,应该会有一个列表用来储存所有可能的走法
1. 先找一颗棋
2. 再找看看它的左边 右边 及上面(三个方向即可)是否也有棋子(若有就接步骤3,没有就回步骤1找下一颗棋子)
3. 若这颗被找到的棋是在原本那颗棋的左边被找到就检查它的左边是否有空格, 右边被找到就检查它的右边是否有空格, 上面被找到就检查它的上面是否有空格
(若有空格就接步骤4,若无就再回步骤1找下一颗棋)
4. 把步骤1找的棋移到步骤3找到的空格,并把步骤2找到的棋子变空格,然后把此步走法到步骤5中去检验
5. 检查这个新走法是否之前已经有被存过(是否有重覆),若有的话就跳步骤1,若没有重覆则跳步骤6
6. 把这个被检查过没有重覆的阵列加入列表中
7. 重覆步骤1~6直到走到了被指定的目的地
本程序方法有二种::
(1)深度优先搜索算法<源代码见附录1>:
对于当前某个棋盘,计算它下一步能走的所有路径,并按顺序保存在一个向量中,由于是深度优先遍历,所以可以设置一个变量iIndexLst记录其按序访问的索引(即先访问第一个,下次再访问第二个),每次访问时要将访问的路径(即要走的棋子的坐标,方向和当前走法的索引值iIndexLst)入栈,以便此分支下无路可走或找到目标点时能够回溯(出栈并恢复棋盘).然后走棋(更新棋盘,设置0,1),不过为了防止iIndexLst访问时越界,需与当前所有走法的最大值进行比较,如果不越界,表明仍有路可走,则继续往前走,进入下一个分支(令iIndexLst= 0).否则表示当前走法已走完,此时要回溯,此处用到了循环, 因为可能会回溯几次,如果不用循环,则会跳出大的while( iIndexLst< vWalk.size()),这肯定是错误的.在回溯时,要出栈,恢复棋盘,重新计算可走路线ComputeWalkable(),并将iIndexLst加1,以表示这条路线已经走完,可以进入下一条路线.
深度优先算法节省内存,只用一个栈记录行走路径,以便回退即可. 但缺点是比较耗时,不适合找最短路径.这个程序我跑了一个晚上都没跑完,存在很大问题,所以后来我改用下面的广度优先搜索算法.如下图
(2)广度优先搜索算法<源代码见附录2>:
此算法是按层次遍历,即先把当前qCurr的走法全部访问完(访问时需计算出下一步的所有走法,并将这些走法全部入队qNext)后再访问下一步的走法.如果当前qCurr访问完毕,则访问下一层(从qNext中取),有点像双缓冲,一前一后相互配合.每次访问时需将当前点和下一步的走法(深度优先用iIndexLst索引记录访问索引值,而此处不用,因为它只需按顺从队列中取即可,效果是一样的)入队qNext.不过还要判断是否到达终点.此程序中将所有的棋子走法全部保存了下来,类似树的结构,而程序中用的是双链表,以便能够从起点到终点对各条路线进行访问.不过如果路径很长,则可能很耗时,所以要剪枝,以避免访问重复的棋盘.如下图:
附录1 深度优先搜索算法 源代码:
// ConsoleTemplate.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
#define m 8 //迷宫的宽
#define n 8 //迷宫的长
typedef struct
{ int x,y;
} item ;
typedef struct
{int x,y,d; //横纵坐标及方向
}DataType ;
typedef struct
{
DataType t;
int iIndex;//当前点在整个向量中的索引,以便恢复
}WalkDataWithIndex;
vector< DataType> vWalk;
typedef stack< WalkDataWithIndex> SeqStack;
int nPathShortest= 1000000;//最短的路径长度
vector< DataType> g_ShortestPathVector;//保存最短的路径经过的点
//计算可走的棋子
void ComputeWalkable( int maze[m ][n ], item *move, vector< DataType> & vWalk);
int mazepath(int maze[m ][n ], item *move, int xE, int yE, vector< DataType> & vWalk)
{
//求迷宫路径，入口参数：maze为指向迷宫数组的指针,move为指向移动方向的指针
//开始点(x0,y0)，到达点(xE,yE)
SeqStack S ;
DataType temp ;
WalkDataWithIndex wkIndexTem;
int x, y, d, i, j ;
int iRowNext1, iColNext1, iRowNext2, iColNext2;
ComputeWalkable( maze, move, vWalk);//计算可走的棋子
bool bFind= false;//是否找到
int iIndexLst= 0;//队列索引
//S.push( temp);//S.Push_Stack(temp) ;
while ( iIndexLst< vWalk.size() )
{
temp= vWalk[ iIndexLst];//按顺序取
//更新棋盘(当前0,当前下一方向0,当前下下一方向1)
iRowNext1= temp.x+move[ temp.d].x;//下一方向
iColNext1= temp.y+move[ temp.d].y;
iRowNext2= iRowNext1+move[ temp.d].x;//下下一方向
iColNext2= iColNext1+move[ temp.d].y;
maze[ temp.x][ temp.y] = 0;
maze[ iRowNext1][ iColNext1]= 0;
maze[ iRowNext2][ iColNext2]= 1;
//当前点及方向入栈,以便恢复
wkIndexTem.t= temp;
wkIndexTem.iIndex= iIndexLst;
S.push( wkIndexTem);
//找到终点
if ( iRowNext2 == xE && iColNext2== yE )
{
static int iNumFind= 0;
cout<<"找到,方法"<< ++iNumFind<<":/n";
SeqStack tmpStk( S) ;
bool bShorter= false;
if ( nPathShortest > S.size())
{
nPathShortest= S.size();
bShorter= true;
}
//输出
while ( !tmpStk.empty())
{
wkIndexTem= tmpStk.top();
tmpStk.pop();
cout<<"("<< wkIndexTem.t.x <<"," << wkIndexTem.t.y<<")," << wkIndexTem.t.d<< endl;
if ( bShorter)//保存最短路径经过的点
{
g_ShortestPathVector.push_back( wkIndexTem.t);
}
}
cout << endl;
bFind= true;
}
int iCurrSize= vWalk.size();
//重新计算可走的棋子
ComputeWalkable( maze , move, vWalk);
bool bBack= false;
if ( !S.empty())
{
while ( ( iIndexLst >= iCurrSize || vWalk.empty() || bFind) && !S.empty())//此路不通,即无子可下
{
{
//当前点及方向入栈,以便恢复
wkIndexTem= S.top();
S.pop();
temp= wkIndexTem.t;
iIndexLst= wkIndexTem.iIndex+ 1;
//恢复
//更新棋盘(当前0,当前下一方向0,当前下下一方向1)
iRowNext1= temp.x+move[ temp.d].x;//下一方向
iColNext1= temp.y+move[ temp.d].y;
iRowNext2= iRowNext1+move[ temp.d].x;//下下一方向
iColNext2= iColNext1+move[ temp.d].y;
maze[ temp.x][ temp.y] = 1;
maze[ iRowNext1][ iColNext1]= 1;
maze[ iRowNext2][ iColNext2]= 0;
//重新计算可走的棋子
ComputeWalkable( maze , move, vWalk);
iCurrSize= vWalk.size();
}
bBack= true;
bFind= false;//是否找到
}
}
if(!bBack)//如果没有回退,则表明下一个新的,从0开始
{
iIndexLst= 0;
//重新计算可走的棋子
ComputeWalkable( maze , move, vWalk);
}
/*else
{
}*/
void ComputeWalkable( int maze[m ][n ], item *move, vector< DataType> & vWalk)
{
vWalk.clear();//先清空队列
DataType temp ;//要放入队列的临时变量
int iRowNext1, iColNext1, iRowNext2, iColNext2;
for ( int iRow= 0; iRow < m; ++iRow)
{
for ( int iCol= 0; iCol < n; ++iCol)
{
for( int iDir= 0; iDir< 4; ++iDir)
{
iRowNext1= iRow+move[ iDir].x;//下一方向
iColNext1= iCol+move[ iDir].y;
iRowNext2= iRowNext1+move[ iDir].x;//下下一方向
iColNext2= iColNext1+move[ iDir].y;
//当前为1,下一方向不出界,且为1,下下一方向不出界,且为0.此时可走,放入队列
if ( ( maze[ iRow][ iCol] == 1) &&
( 0 <= iRowNext1 && iRowNext1 < m
&& 0 <= iColNext1 && iColNext1 < n && maze[ iRowNext1][ iColNext1] == 1) &&
( 0 <= iRowNext2 && iRowNext2 < m
&& 0 <= iColNext2 && iColNext2 < n && maze[ iRowNext2][ iColNext2] == 0))
{
temp.x= iRow;//保存当前可走点和方向
temp.y= iCol;
temp.d= iDir;
vWalk.push_back( temp);//可走的点入队列
}
}
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int maze [m][n]=
{
{ 0, 0, 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 0, 0, 0, 0},
{ 1, 1, 1, 1, 1, 1, 1, 1},
{ 1, 1, 1, 1, 1, 1, 1, 1},
{ 1, 1, 1, 1, 1, 1, 1, 1},
{ 1, 1, 1, 1, 1, 1, 1, 1}
} ;
/*int maze [m][n]=
{
{ 1, 1, 0, 1},
{ 0, 0, 0, 1},
{ 1, 1, 1, 1},
{ 1, 1, 1, 1}
} ; */
/*int maze [m][n]=
{
{ 0, 0, 0, 0},
{ 0, 0, 0, 0},
{ 1, 1, 1, 1},
{ 1, 1, 1, 1}
} ; */
/*int maze [m][n]=
{
{ 1, 0, 0, 0},
{ 0, 1, 0, 0},
{ 1, 1, 0, 0},
{ 0, 0, 0, 0}
} ; */
/*int maze [m][n]=
{
{ 1, 1, 0, 0},
{ 0, 0, 1, 0},
{ 1, 0, 1, 0},
{ 0, 0, 0, 0}
} ; */
item move[4]=
{
{ 0, 1},
{ 1, 0},
{ 0,-1},
{-1, 0}
};
mazepath( maze, move, 1, 4, vWalk);
cout <<"最短路径为:/n";
for ( int i= 0; i< g_ShortestPathVector.size(); ++i)
{
cout<<"("<< g_ShortestPathVector[ i].x <<"," << g_ShortestPathVector[ i].y<<")," << g_ShortestPathVector[ i].d<< endl;
}
system("pause");
return 0;
}
附录2 广度优先搜索算法 源代码:
// ConsoleTemplate.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
#include <list>
#include <vector>
#include <cmath>
#include <map>
using namespace std;
#define m 8 //迷宫的宽
#define n 7 //迷宫的长
typedef struct
{ int x,y;
} item ;
struct DataType
{int x,y,d; //横纵坐标及方向
DataType* next; //前后指针，组成双链表
DataType*pre;
} ;
typedef vector< int> VI;
typedef vector< VI> VVI;
typedef list< DataType*> MyQueue;//队列
MyQueue qCurr, qNext;//;当前可走队列,和下一队列
map< __int64, bool> bsExits;//用于去掉重复的,初始为0表示没访问,后如果//为1表示已访问当前棋盘,则不再重复访问
int nPathShortest= 1000000;//最短的路径长度
vector< DataType> g_ShortestPathVector;//保存最短的路径经过的点
//计算可走的棋子
void ComputeWalkable( VVI maze, item *move, DataType* pCur, MyQueue & qNext);
int mazepath( VVI maze, item *move, int xE, int yE, MyQueue & qCurr, MyQueue & qNext )
{
//求迷宫路径，入口参数：maze为指向迷宫数组的指针,move为指向移动方向的指针
//开始点(x0,y0)，到达点(xE,yE)
VVI mazeStartConst( maze);
DataType *pTemp, *pHead, *pHeadNext= NULL;
//WalkDataWithIndex wkIndexTem;
int iRowNext1, iColNext1, iRowNext2, iColNext2;
ComputeWalkable( maze, move, NULL, qCurr);//计算可走的棋子,先放入前队列
while ( true)
{
if ( !qCurr.empty())//如果队列不空，则表示有棋子可走
{
pTemp= *qCurr.begin();
qCurr.pop_front();//出队
//更新棋盘
iRowNext1= pTemp->x+move[ pTemp->d].x;//下一方向
iColNext1= pTemp->y+move[ pTemp->d].y;
iRowNext2= iRowNext1+ +move[ pTemp->d].x;//下下一方向
iColNext2= iColNext1+ +move[ pTemp->d].y;
if ( iRowNext2 == xE && iColNext2== yE)//找到目标
{
cout<<"找到/n";
//输出
//走棋的第一步
pHead= pTemp;
while ( pHead != NULL && pHead->pre != NULL)//第一步
{
pHead->pre->next= pHead;//修改下一个指针
//pHeadNext= pHead;
pHead= pHead->pre;
}//总可以找到pHead
maze= mazeStartConst;//从棋盘最初开始
int iNumStep= 0;//步骤个数
//更新棋盘到当前状态(从固定的初始状态开始)
while ( pHead != pTemp->next)
{
//更新棋盘
iRowNext1= pHead->x+move[ pHead->d].x;//下一方向
iColNext1= pHead->y+move[ pHead->d].y;
iRowNext2= iRowNext1+ +move[ pHead->d].x;//下下一方向
iColNext2= iColNext1+ +move[ pHead->d].y;
maze[ pHead->x][ pHead->y] = 0;
maze[ iRowNext1][ iColNext1]= 0;
maze[ iRowNext2][ iColNext2]= 1;
cout<<"第"<< ++iNumStep << "步: "<<"棋子为:("<< pHead->x <<"," << pHead->y<<"),方向:" << pHead->d<< endl;
pHead= pHead->next;
for ( int i= 0; i< m; ++i)
{
for ( int j= 0; j< n; ++j)
{
cout << maze[ i][ j]<<" ";
}
cout << endl;
}
cout << endl;
}
return 1;
}
//走棋的第一步
pHead= pTemp;
while ( pHead != NULL && pHead->pre != NULL)//第一步
{
pHead->pre->next= pHead;//修改下一个指针
//pHeadNext= pHead;
pHead= pHead->pre;
}//总可以找到pHead
//pHead->next= pHeadNext;
maze= mazeStartConst;//从棋盘最初开始
//更新棋盘到当前状态(从固定的初始状态开始)
while ( pHead != pTemp->next)
{
//更新棋盘
iRowNext1= pHead->x+move[ pHead->d].x;//下一方向
iColNext1= pHead->y+move[ pHead->d].y;
iRowNext2= iRowNext1+ +move[ pHead->d].x;//下下一方向
iColNext2= iColNext1+ +move[ pHead->d].y;
maze[ pHead->x][ pHead->y] = 0;
maze[ iRowNext1][ iColNext1]= 0;
maze[ iRowNext2][ iColNext2]= 1;
pHead= pHead->next;
}
__int64 iNumCur= 0;
//剪枝,去掉重复的
for ( int iRow= 0; iRow < m; ++iRow)
{
for ( int iCol= 0; iCol < n; ++iCol)
{
iNumCur= iNumCur* 2+ maze[ iRow][ iCol];
}
}
//如果该棋盘没有遍历到,则遍历
if ( bsExits[ iNumCur] == 0)
{
ComputeWalkable( maze, move, pTemp, qNext);//计算可走的棋子,先放入前队列
bsExits[ iNumCur] = 1;//该棋盘已遍历到
}
else
{
int i= 0;
++i;
}
}
else//当前队列qCurr遍历完毕
{
if ( !qNext.empty())//下一队列仍有值，则复制到前队列qCurr中
{
qCurr= qNext;//复制
qNext.clear();//后队列清空
}
else
{
break;//整个程序遍历完毕，跳出
}
}
}//while
return 0 ;//迷宫
}
void ComputeWalkable( VVI maze, item *move, DataType* pCur, MyQueue & qNext)
{
//DataType temp ;//要放入队列的临时变量
int iRowNext1, iColNext1, iRowNext2, iColNext2;
for ( int iRow= 0; iRow < m; ++iRow)
{
for ( int iCol= 0; iCol < n; ++iCol)
{
for( int iDir= 0; iDir< 4; ++iDir)
{
iRowNext1= iRow+move[ iDir].x;//下一方向
iColNext1= iCol+move[ iDir].y;
iRowNext2= iRowNext1+move[ iDir].x;//下下一方向
iColNext2= iColNext1+move[ iDir].y;
//当前为,下一方向不出界,且为,下下一方向不出界,且为.此时可走,放入队列
if ( ( maze[ iRow][ iCol] == 1) &&
( 0 <= iRowNext1 && iRowNext1 < m
&& 0 <= iColNext1 && iColNext1 < n && maze[ iRowNext1][ iColNext1] == 1) &&
( 0 <= iRowNext2 && iRowNext2 < m
&& 0 <= iColNext2 && iColNext2 < n && maze[ iRowNext2][ iColNext2] == 0))
{
//建立双链表
DataType* pNew= new DataType();
//通过某个方向d,走到新点iRowNext2
pNew->d= iDir;
pNew->x= iRow;
pNew->y= iCol;
pNew->next= NULL;//后指针为空
pNew->pre= pCur;//前指针
if ( pCur != NULL)//不是第一步
{
pCur->next= pNew;//后指针
}
qNext.push_back( pNew);//可走的点入队列
}
}
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
/*int imaze [m][n]=
{
{ 0, 0, 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 0, 0, 0, 0},
{ 1, 1, 1, 1, 1, 1, 1, 1},
{ 1, 1, 1, 1, 1, 1, 1, 1},
{ 1, 1, 1, 1, 1, 1, 1, 1},
{ 1, 1, 1, 1, 1, 1, 1, 1}
} ; */
/*int imaze [m][n]=
{
{ 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 1, 0, 0},
{ 0, 0, 0, 0, 0, 0, 0},
{ 0, 1, 1, 1, 1, 1, 0},
{ 0, 0, 0, 1, 1, 0, 1},
{ 1, 0, 1, 0, 1, 0, 0},
{ 0, 1, 0, 0, 0, 0, 1}
} ; */
/*int imaze [m][n]=
{
{ 0, 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 0, 0, 0},
{ 1, 0, 1, 1, 1, 1, 1},
{ 0, 0, 1, 1, 1, 1, 1},
{ 0, 0, 1, 1, 1, 0, 1},
{ 1, 0, 1, 0, 1, 0, 1}
} */;
int imaze [m][n]=
{
{ 0, 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 0, 0, 0},
{ 1, 1, 1, 1, 1, 1, 1},
{ 1, 1, 1, 1, 1, 1, 1},
{ 1, 1, 1, 1, 1, 1, 1},
{ 1, 1, 1, 1, 1, 1, 1}
} ;
/*int imaze [m][n]=
{
{ 1, 1, 0, 1},
{ 0, 0, 0, 1},
{ 1, 1, 1, 1},
{ 1, 1, 1, 1}
} ; */
/*int imaze [m][n]=
{
{ 0, 0, 0, 0},
{ 0, 0, 0, 0},
{ 1, 1, 1, 1},
{ 1, 1, 1, 1}
} ; */
/*int imaze [m][n]=
{
{ 1, 0, 0, 0},
{ 0, 1, 0, 0},
{ 1, 1, 0, 0},
{ 0, 0, 0, 0}
} ; */
/*int imaze [m][n]=
{
{ 1, 1, 0, 0},
{ 0, 0, 1, 0},
{ 1, 0, 1, 0},
{ 0, 0, 0, 0}
} ; */
/*int imaze [m][n]=
{
{ 1, 0, 0, 0},
{ 0, 1, 1, 0},
{ 1, 1, 0, 0},
{ 0, 0, 1, 0}
} ; */
cout <<"原棋盘为:"<< endl;
VVI maze( m, VI( n));
for ( int i= 0; i< m; ++i)
{
for ( int j= 0; j< n; ++j)
{
maze[ i][ j]= imaze[ i][ j];
cout << maze[ i][ j]<<" ";
}
cout << endl;
}
item move[4]=
{
{ 0, 1},
{ 1, 0},
{ 0,-1},
{-1, 0}
};
mazepath( maze, move, 1, 4,/*1, 4,*/ qCurr, qNext);
system("pause");
return 0;
}