解题报告——2018级2016第二学期第二周作业

D：迷宫问题

题目描述：

定义一个二维数组： 

int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

输入

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

输出

左上角到右下角的最短路径，格式如样例所示。

样例输入

0 1 0 0 0

0 1 0 1 0

0 0 0 0 0

0 1 1 1 0

0 0 0 1 0

样例输出

(0, 0)

(1, 0)

(2, 0)

(2, 1)

(2, 2)

(2, 3)

(2, 4)

(3, 4)

(4, 4)

分析：

这题可以用宽搜来做，但是我们要多开一数组来存储这个点的前点；

我没有用二维的dl数组，而是分别开了x,y,pp数组；

同其他宽搜一样在选择路径中用循环路径表；

一开始我多开了一个数组来储存这个点的序号，但我发现这样比麻烦，而且容易出错，所以，后来我用了f，p来表示当前和以后的序号；

在输出是我用了递归函数，从p开始一直到pp【t】==1（注意不是==0，否则会有两个（0,0））时print（pp【t】）在其后面加上输出；

因为是递归所以自然会倒叙输出；

代码：

#include<cstdio>#include<cmath>#include<iostream>#include<cstdlib>#include<cstring>

using namespace std;

int   tu[100][100];const int dx[4]={0,0,1,-1};const int dy[4]={1,-1,0,0};int x[100],y[100],pp[100];//行，列，前点

int  print(int t){//递归函数

    if(t!=1)

        print(pp[t]);

    cout<<"("<<x[t]<<", "<<y[t]<<")"<<endl;}

int main(){

     for(int i=0;i<5;i++)

        for(int j=0;j<5;j++)

        cin>>tu[i][j];//读入

     int f=1,p=2;

     x[1]=0;y[1]=0;pp[0]=0;

     tu[0][0]=1;

     bool flag=true;

     while(f<p&&flag){

        for(int i=0;i<4;i++){

            int hh=x[f]+dx[i];

            int ll=y[f]+dy[i];

            if(tu[hh][ll]==0&&hh>=0&&hh<5&&ll>=0&&ll<5){//可能性判断

                pp[p]=f;

                x[p]=hh;

                y[p]=ll;

                tu[hh][ll]=1;

                if(hh==4&&ll==4){flag =false;break;}//判断终点

                p++;

            }

        }

        f++;

     }

     print(p);//输出

     return 0;}

算法：宽搜；

解题报告——2018级2016第二学期第二周作业