用循环和递归处理迷宫问题

1. 用循环解决迷宫问题
先看下图的迷宫

这里的1代表墙，0代表通道。（只解决简单的迷宫是否有出口问题或者输出一条路径）
首先我们需要接收这样一个迷宫，那就定义一个二维数组来保存它。

#define N 10
int maze[N][N];
void GetMaze(int *arr, int n)
{
    FILE *f = fopen("test.txt","r");//test.txt里保存的是迷宫
    assert(f);
for(int i = 0;i<N; i++)
    {
for(int j = 0; j<N; )
        {
int a = fgetc(f)-'0';//读出来的是字符，所以要减去字符0
if(a == 1||a == 0)//只有当读取到0和1是将它放进数组，空格和其他字符则跳过
            {
                arr[i*n+j] = a;
                j++;
            }
else if(arr[i*n+j] == EOF)
            {
                exit(0);
            }

        }
    }
}

然后还要保证能输出迷宫

void PrintMaze(int* arr, int n)
{
    assert(arr);
for(int i = 0; i<n; i++)
    {
for(int j = 0; j<n; j++)
        {
cout<<arr[i*n+j]<<" ";
        }
cout<<endl;
    }
}

接着我们定义一个储存结构体类型的栈，保存通路的路径。

struct Pos
{
int _row;//行
int _col;//列
};
stack<Pos> path;

每走一步，若此步可通，就将其坐标压入栈中，不通则不入栈。
具体过程在下面代码中实现。

#include<iostream>
#include<stack>
#include<assert.h>

using namespace std;
#define N 10

struct Pos
{
int _row;//行
int _col;//列
};

void GetMaze(int *arr, int n)//接受地图
{
    FILE *f = fopen("test.txt","r");//地图放在当前文件的“test.txt”下
//assert(f);
for(int i = 0;i<N; i++)
    {
for(int j = 0; j<N; )
        {
int a = fgetc(f)-'0';
if(a == 1||a == 0)
            {
                arr[i*n+j] = a;
                j++;
            }
else if(arr[i*n+j] == EOF)//判断地图地图是否完整
            {
exit(0);
            }

        }
    }
}

bool CheckIsAccess(int *arr, int n, Pos next,stack<Pos> path)//判断坐标是否合法
{
if(next._row>=0 && next._row<n 
        && next._col>=0 && next._col < n
            && arr[next._row*n+next._col] == 0
            && (next._col != path.top()._col 
            ||next._row != path.top()._row))//此坐标不能越界且不能栈顶的坐标相同
    {
return true;
    }
return false;
}

bool GetMazePath(int *arr, int n, Pos entry, stack<Pos> path)//找出口
{
    assert(arr);
    path.push(entry);//先将入口压栈
    arr[entry._row*n+entry._col] = 2;//将走过的路标记
    Pos cur, next;
while(!path.empty())//判断栈是否为空来决定循环的结束
    { 

        cur = path.top();//栈顶的元素说明当前这步可通，接下来就是判断这步是不是出口或者其四个方向是否有通路
if(cur._row == n-1)//判断这步是不是出口
return true;

//判断此步的上方是否可通
        next._col = cur._col;
        next._row = cur._row-1;
if(CheckIsAccess(arr, n, next, path))
        {
            path.push(next);
            arr[next._row*n + next._col] = 2;
continue;
        }
//判断此步的右方是否可通
        next._col = cur._col+1;
        next._row = cur._row;
if(CheckIsAccess(arr, n, next, path))
        {
            path.push(next);
            arr[next._row*n + next._col] = 2;
continue;
        }

//判断此步的下方是否可通
        next._col = cur._col;
        next._row = cur._row+1;
if(CheckIsAccess(arr, n, next, path))
        {
            path.push(next);
            arr[next._row*n + next._col] = 2;
continue;
        }

//判断此步的左方是否可通
        next._col = cur._col-1;
        next._row = cur._row;
if(CheckIsAccess(arr, n, next, path))
        {
            path.push(next);
            arr[next._row*n + next._col] = 2;
continue;
        }

        path.pop();//当程序运行到这儿时说明此路不通，将此步删除
    }
return false;
}

void PrintMaze(int* arr, int n)//打印迷宫
{
    assert(arr);
for(int i = 0; i<n; i++)
    {
for(int j = 0; j<n; j++)
        {
cout<<arr[i*n+j]<<" ";
        }
cout<<endl;
    }
}
int main()
{
int arr[N][N];
    Pos entry = {2,0};//入口
stack<Pos> path;
    GetMaze((int*)arr, N);
cout<<"是否找到迷宫的出口？"<<GetMazePath((int*)arr, N, entry, path)<<endl;
    PrintMaze((int*)arr, N);
return 0;
}

运行结果：

图中标为2 的就是所走路径。

2.用递归解决迷宫问题
用递归求解迷宫只需将循环部分改为递归即可。
代码如下：

#include<iostream>
#include<stack>
#include<assert.h>

using namespace std;
#define N 10

struct Pos
{
int _row;//行
int _col;//列
};

void GetMaze(int *arr, int n)//接受地图
{
    FILE *f = fopen("test.txt","r");//地图放在当前文件的“test.txt”下
    assert(f);
for(int i = 0;i<N; i++)
    {
for(int j = 0; j<N; )
        {
int a = fgetc(f)-'0';
if(a == 1||a == 0)
            {
                arr[i*n+j] = a;
                j++;
            }
else if(arr[i*n+j] == EOF)//判断地图地图是否完整
            {
exit(0);
            }

        }
    }
}

bool CheckIsAccess(int *arr, int n, Pos next,stack<Pos> path)//判断坐标是否合法
{
if(next._row>=0 && next._row<n 
        && next._col>=0 && next._col < n
            && arr[next._row*n+next._col] == 0
            && (next._col != path.top()._col 
            ||next._row != path.top()._row))//此坐标不能越界且不能栈顶的坐标相同
    {
return true;
    }
return false;
}

void GetMazePath(int *arr, int n, Pos entry, stack<Pos>& path)//找出口
{
    assert(arr);
    path.push(entry);//先将入口压栈
    arr[entry._row*n+entry._col] = 2;//将走过的路标记
    Pos cur, next;

    cur = path.top();//栈顶的元素说明当前这步可通，接下来就是判断这步是不是出口或者其四个方向是否有通路
if(cur._row == n-1)//判断这步是不是出口
    {
return;
    }


//判断此步的上方是否可通
    next._col = cur._col;
    next._row = cur._row-1;
if(CheckIsAccess(arr, n, next, path))//判断是否合法
    {

        arr[next._row*n + next._col] = 2;//标记这一步
        GetMazePath(arr, n, next, path);//递归调用，将此步认为是当前入口
    }
//右
    next._col = cur._col+1;
    next._row = cur._row;
if(CheckIsAccess(arr, n, next, path))
    {

        arr[next._row*n + next._col] = 2;
        GetMazePath(arr, n, next, path);
    }

//下
    next._col = cur._col;
    next._row = cur._row+1;
if(CheckIsAccess(arr, n, next, path))
    {

        arr[next._row*n + next._col] = 2;
        GetMazePath(arr, n, next, path);
    }

//左
    next._col = cur._col-1;
    next._row = cur._row;
if(CheckIsAccess(arr, n, next, path))
    {

        arr[next._row*n + next._col] = 2;
        GetMazePath(arr, n, next, path);
    }
if(path.top()._row != n-1)
    path.pop();
}

void PrintMaze(int* arr, int n)
{
    assert(arr);
for(int i = 0; i<n; i++)
    {
for(int j = 0; j<n; j++)
        {
cout<<arr[i*n+j]<<" ";
        }
cout<<endl;
    }
}
int main()
{
int arr[N][N];
    Pos entry = {2,0};//入口
stack<Pos> path;
    GetMaze((int*)arr, N);
    GetMazePath((int*)arr, N, entry, path);
cout<<"是否找到迷宫的出口？"<<!path.empty()<<endl;//根据栈是否为空来判断是否找到出口
    PrintMaze((int*)arr, N);
return 0;
}

结果：

完！