01.问题描述

涂抹横向和纵向排列的n×*n *个方格中的几个，制作成迷宫。这里规定被涂抹的方格是墙壁，没有被涂抹的就是道路。

两人分别从A点和B 点同时出发，每次前进1 个方格，且按照“右手法则”前进。所谓右手法则，就是靠着右边墙壁前进，不一定要按最短路径前进，但最终要回到入口或者到达出口（其中一人从A 点出发向B 点前进，另一人从B点出发向A 点前进。A 点和B点的位置固定，假设就是左上角和右下角）。求当n=5时，两人在途中相遇的情况一共有多少种？同时到达同一点算相遇，其中一人到达终点，另一人同时回到这个位置也算。

举个例子，当n ＝ 4 时，①的情况下两人可以相遇，②的情况下两人就不能相遇（①的情况下，如果A 像“↓↓↑→→↓↓←→→”这样移动，而B 像“←↑↑→←↑↓←←↑”这样移动，在第5 次移动时两人就会相遇）。

n=4时的示意图

02.算法分析与设计

1）算法分析

解决问题的关键在于“怎样实现用右手法则进行搜索”。首先用0 表示道路，用1 表示墙壁，通过设置0 和1 表示迷宫。那么问题就变成了求有多少种设置方法能使按照右手法则在迷宫中前进的两人相遇。为实现右手法则搜索，要设置一个按右、上、左、下排列，表示移动方向的数组，并且改变这个数组的索引。譬如目前的移动方向是“上”，那么接下来就要按照右、上、左的顺序来依次搜索；如果目前的移动方向是“左”，那么接下来就要按照上、左、下的顺序来搜索，即按逆时针方向进行搜索。

逆时针搜索

当n ＝ 4 时，上述处理几乎可以瞬间完成，但本题里n ＝ 5，所以就要稍微多花费一些时间了。这里可以通过在搜索前判断迷宫是否有效（能否到达目标）的方式优化。如果搜索前就进行判断，那么只需要搜索225＝ 33554432 种情况中的1225194 种即可，只占全部情况的约3.6%。不过，判断迷宫是否有效也需要一定时间。

2）算法设计

利用5x5的二维数组表示迷宫，用0表示迷宫可通、用1表示不可通的墙壁，则总共有225种情况，对每一种情况进行判断，判断迷宫是否有效，即能否从左上角走到右下角（初始时左上角A的方向向下，右下角B的方向向上），若迷宫有效再按右手法则进行搜索，看A、B是否可以相遇，若A、B相遇则计数加一，若不能相遇则判断下一种情况，直到全部的225种情况判断完成为止。算法主要流程图如下：

算法流程图

关键函数设计

本算法的关键函数主要有三个，分别为exchange()、enable()和search()。其中第一个函数将整数的位转换为迷宫数组，第二个函数判断迷宫能否从A点走到B点（左上角走到右下角），第三个函数在迷宫有效的前提下判断按右手法则搜索A、B能否相遇。

exchange()函数利用简单的位运算或者取余法（用栈作辅助）很容易就实现了。

enable()函数首先判断是否有左上角或者右下角的值为1，若有则应该直接返回false，因为这种情况无论如何也不能从A走到B。剩下的情况利用经典的走迷宫算法进行判断，迷宫入口设置为左上角，出口为右下角。若能走到右下角则返回true，当辅助栈为空时还没有碰到右下角坐标则说明当前迷宫无效，返回false。

search()函数在迷宫有效的前提下判断按右手法则搜索，A与B能否相遇，若相遇返回true，否则返回false。这是本算法最核心的函数，为了便于更好的展示该函数的思想和步骤，画了如下的流程图：

search()函数流程图

03.源代码

#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());
}//运行成功 N==5时 一共有660148种满足条件的迷宫 2019年5月1日3:02:11

04.测试结果

测试结果

05.参考文献

[1] 增井敏克[日]. 《程序员的算法趣题》，人民邮电出版社，2017年；