#include<stdio.h>
#define N (5)
#include<stack>
using namespace std;
bool mark[N][N];
typedef struct Pos{
//位置结构体
int i, j;
void set(int i, int j)
{
this->i = i;
this->j = j;
}
}POS;
bool IsPos(const int maze[][N], int i, int j)
{//判断迷宫位置是否合法及是否已经走过
if (i >= 0 && i < N && j >= 0 && j < N &&maze[i][j] == 0 &&mark[i][j] == true)
return true;
else
return false;
}
bool enable(const int maze[][N])
{//判断迷宫能否从左上角走到右下角
if(maze[0][0] == 1 || maze[N-1][N-1] == 1) return false;//左上角和右下角为1则迷宫一定不可通
stack<POS> S;
for(int i=0;i<N;++i)//初始标记数组
{
for(int j=0;j<N;++j)
mark[i][j] = true;
}
mark[0][0] = false;//设置左上角已经走过
POS ps; ps.set(0, 0);
S.push(ps);
int pos[4][2] = { -1, 0, 0, 1, 1, 0, 0, -1 };
while (!S.empty())
{
ps = S.top();
bool is = false;
for (int k = 0; k < 4; ++k)
{
if (IsPos(maze, ps.i + pos[k][0], ps.j + pos[k][1]))//依次判断迷宫4个方向的走位
{
ps.i += pos[k][0]; ps.j += pos[k][1];
if(ps.i == N-1 && ps.j ==N-1)//如果已经走到右下角，返回true
return true;
mark[ps.i][ps.j] = false;
S.push(ps);
is = true;
break;
}
}
if (!is)
{
S.pop();
}
}
return false;//没有走通，返回false
}
void show(int maze[][N])
{//打印迷宫方便调试
for(int i=0;i<N;++i)
{
for(int j=0;j<N;++j)
printf("%d ", maze[i][j]);
putchar('\n');
}
}
void exchange(int maze[][N], int n)
{//将n转换成数组保存的迷宫，0为路，1为墙
for(int i=N-1;i>=0;--i)
{
for(int j=N-1;j>=0;--j)
{
maze[i][j] = n&1;
n>>=1;
}
}
/*取余法将n转换为数组保存的迷宫
stack<int> S;
while(n)
{
S.push(n % 2);
n /= 2;
}
while(S.size()< N*N)
S.push(0);
int cnt=0;
int i,j;
i=j=0;
while(!S.empty())
{
maze[i][j] = S.top();
j++;
++cnt;
if(cnt == N)
{
j=0;++i;
cnt = 0;
}
S.pop();
}
*/
}
bool IsPos2(const int maze[][N], int i, int j)
{//判断位置i、j迷宫是否可通
if (i >= 0 && i < N && j >= 0 && j < N &&maze[i][j] == 0)//判断该位置是否可通
return true;
else
return false;
}
bool search( int maze[][N])
{
//判断按右手法则搜索A、B能否相遇，相遇返回true否则返回false
int pos[4][2] = { 0, 1, -1, 0, 0, -1, 1, 0 };
POS ps1,ps2;
ps1.set(0,0);//初始化A位置
ps2.set(N-1,N-1);//初始化B位置
int d1,d2;//d1、d2表示方向，0表示向右，1向上，2向左，3向下
d1=3;d2=1;//初始化方向，其中d1为A的方向，d2为B的方向，初始时A向下，B向上
while(1)
{
do{
if(IsPos2(maze, ps1.i+pos[d1][0],ps1.j+pos[d1][1]))//按当前方向A是否可以走到下一个位置
{
ps1.i+=pos[d1][0];ps1.j+=pos[d1][1];//按当前方向A可以走到下一个位置，更新位置
d1 = (d1-1+4)%4;//更新方向为当前方向的右手边方向
break;//A走了一步，跳出循环
}
else//按当前方向A不可以走到下一个位置（有墙或者出了迷宫）
d1 = (d1+1+4)%4;//按逆时针更新方向
}while(1);
do{//同理对B进行上述操作
if(IsPos2(maze, ps2.i+pos[d2][0],ps2.j+pos[d2][1]))
{
ps2.i+=pos[d2][0];ps2.j+=pos[d2][1];
d2 = (d2-1+4)%4;
break;
}
else
d2 = (d2+1+4)%4;
}while(1);
if(ps1.i == ps2.i && ps1.j == ps2.j)//A、B相遇，返回1
return 1;
if((ps1.i == N -1 && ps1.j ==N-1) || (ps2.i == 0 && ps2.j==0) )//A、B有一个先到达终点，不可能相遇，返回0
return 0;
}
}
int count()
{//计数函数，返回A、B相遇的迷宫模式数量
int maze[N][N];
int mazeI;
int cnt = 0;
for(mazeI=0; mazeI< (1<<N*N); ++mazeI)//对所有可能的迷宫进行检验（总共2^(N*N)个迷宫）
{
exchange(maze, mazeI);
if(enable(maze))
{
if(search(maze))
++cnt;
}
}
return cnt;
}
int main()
{
printf("当n=%d时，一共有%d种满足条件的迷宫。\n",N,count());
}
分享
