cpp春实验二

---

实验目的

研究指针和动态内存分配的使用。要求完善所给程序来穿越迷宫。迷宫可以由字符数组表示，如：

  0 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7
 0# # # # # # # # # # # # # . # # #
 1# . . . . . . . . . . . # . # . #
 2# # # # # . # # # # # # # . # . #
 3# . . . . . # . . . . . . . # . #
 4# . # # # # # . # # # # # # # . #
 5# . # . . . . . # . . . # . . . #
 6# . # . # # # # # . # . # . # . #
 7# . # . . . . . . . # . # . # . #
 8# . # # # # # # # . # # # . # . #
 9# . . . # . . . # . . . . . # . #
10# . # . # . # . # # # # # . # . #/
11# . # . . . # . # . # . . . # . #
12# # # # # # # . # . # . # . # # #
13# . . . . . # . # . . . # . . . #
14# . # # # . # . # . # # # . # . #
15# . . . # . . . . . # . . . # . #
16# # # # # # # # # # # # # # # . #

实验原理

根据只沿着墙靠右走就能走出迷宫的方法求解：若右手有墙则直走，否则向右转向。在图像中，入口默认在上，出口默认在下。墙壁为#，通路为.。在程序中，Direction表示朝向，每个朝向都与一个右向对应，由此设计出程序

实验要求任务

任务1：

完成$maze.cpp$中空余的四个函数，以完成迷宫的探索

如下

void TurnRight(Direction& heading)
{
    if(heading ==DOWN)//左变
    heading =LEFT;
    else if(heading ==RIGHT)
    heading =DOWN;
    else if(heading ==UP)
    heading =RIGHT;
    else if(heading ==LEFT)
    heading =UP;
}

//  This function changes position in the maze by determining
//  the next position in the current direction

void MoveForward(int& pos, Direction heading)
{
    switch (heading) 
    {
    case DOWN:
        {
            pos+=mazeWidth;
            break;
        }
    case LEFT:
        {
            pos--;
            break;
        }
    case UP:
        {
            pos-=mazeWidth;
            break;
        }
    case RIGHT:
        {
            pos++;
        }
    }
}
void WheresAhead(int pos, Direction heading, int& ahead)
{
    ahead=pos;
    if(heading ==DOWN)//右手在左，面朝下
    ahead+=mazeWidth;
    else if(heading ==RIGHT)//右手在下，面朝右
    ahead++;
    else if(heading ==UP)//右手在右，面朝上
    ahead-=mazeWidth;
    else if(heading ==LEFT)//右手在上，面朝左
    ahead--;
}

//  This function changes heading by turning left

void TurnLeft(Direction& heading)
{
    if(heading==DOWN)
    heading=RIGHT;
    else if(heading==LEFT)
    heading=DOWN;
    else if(heading==RIGHT)
    heading=UP;
    else if(heading==UP)
    heading=LEFT;
}

该任务中，主要函数已经完成，需要补充转向，探路，判断，前进四个函数，完成如上

右转探索阶段

void TurnRight(Direction& heading)
{
    if(heading ==DOWN)//左变
    heading =LEFT;
    else if(heading ==RIGHT)
    heading =DOWN;
    else if(heading ==UP)
    heading =RIGHT;
    else if(heading ==LEFT)
    heading =UP;
}

该函数为右手处无墙时的转向，根据朝向和右手的对应关系，可以把变换一一对应起来

在heading有墙，而右手无墙（即可以向右转）时使用，改变朝向，进行下一步行进。

void MoveForward(int& pos, Direction heading)
{
    switch (heading) 
    {
    case DOWN:
        {
            pos+=mazeWidth;
            break;
        }
    case LEFT:
        {
            pos--;
            break;
        }
    case UP:
        {
            pos-=mazeWidth;
            break;
        }
    case RIGHT:
        {
            pos++;
        }
    }
}

该函数为对当前朝向进行判断，根据地图的上下左右，生成对应的前进坐标

左转出死路阶段

void WheresAhead(int pos, Direction heading, int& ahead)
{
    ahead=pos;
    if(heading ==DOWN)//右手在左，面朝下
    ahead+=mazeWidth;
    else if(heading ==RIGHT)//右手在下，面朝右
    ahead++;
    else if(heading ==UP)//右手在右，面朝上
    ahead-=mazeWidth;
    else if(heading ==LEFT)//右手在上，面朝左
    ahead--;
}

此为根据朝向判断行进步骤的函数，走出死路或无法右转时使用

void TurnLeft(Direction& heading)
{
    if(heading==DOWN)
    heading=RIGHT;
    else if(heading==LEFT)
    heading=DOWN;
    else if(heading==RIGHT)
    heading=UP;
    else if(heading==UP)
    heading=LEFT;
}

当heading有墙，右手无法走通，就要左转，实际上，也可以理解为以heading为右，故往左转。

对$maze1.txt$,有结果如下

Maze File: maze1.txt
（太多不水了
total steps:206
Maze solved

任务2

完成回溯，输出直接到达结果的路径

如下

void SolveMaze()
{   
    int pos, other;
    Direction heading;
    
    FindEntrance(pos);
    heading = DOWN;
    while (!AtExit(pos))
    {
        posi[i]=pos;
        post[pos]++;
        i++;
        if(i>=mazeHeight*mazeWidth)
        {
            cout<<"array too small\n";
            abort();//return0；
        }//越界判断
        WheresRight(pos,heading,other);//将面向方向右侧位置传给other
        if (!Wall(other))//右侧无墙，转向右
        {
            TurnRight(heading);//转向
            MoveForward(pos,heading);//在转向后迈步
        }  
        else//是墙，直走
        {
            WheresAhead(pos,heading,other);//生成直走方向
            if (!Wall(other))//前方有路
                MoveForward(pos,heading);//走一步
            else//右边是墙，面前是墙，使当前左转
                TurnLeft(heading);
        }
    }
    posi[i]=pos;
    i++;
    if(i>=mazeHeight*mazeWidth)
    {
        cout<<"array too small\n";
        abort();
    }
    int counter=0;
    int counter_dir=0;
    for(int j=0;j<i;j++)
    {
        if(posi[j]<0)
            continue;
        if(post[posi[j]]>=2)
        {
            int empt=posi[j];
            int cut_num=post[empt]-1;
            int now_num=0;
            for(int h=j+1;h<i;h++,counter_dir++,counter++)
            {
                if(posi[h]==empt)
                {
                    now_num++;
                    if(now_num==cut_num)
                    {
                        j=h;
                        counter++;
                        counter_dir++;
                        break;
                    }
                }
            }
        }
        cout << "Current position: (" << posi[j]/mazeWidth << ',' << posi[j]%mazeWidth << ')' << endl;
        counter++;
    }
    cout<<"total steps:"<<counter<<endl;
    cout<<"directory steps:"<<counter-counter_dir<<endl;
    cout << "Maze solved" << endl;
    delete maze;
    delete posi;
    delete post;
}

对输入时的计入进行修改，添加数组post表示该节点走过的次数，在输出时回溯走过次数超过1次的节点，就能避免走回头路。

posi[i]=pos;
i++;
if(i>=mazeHeight*mazeWidth)
{
    cout<<"array too small\n";
    abort();
}
int counter=0;
int counter_dir=0;
for(int j=0;j<i;j++)
{
    if(posi[j]<0)
        continue;
    if(post[posi[j]]>=2)
    {
        int empt=posi[j];
        int cut_num=post[empt]-1;
        int now_num=0;
        for(int h=j+1;h<i;h++,counter_dir++,counter++)
        {
            if(posi[h]==empt)
            {
                now_num++;
                if(now_num==cut_num)
                {
                    j=h;
                    counter++;
                    counter_dir++;
                    break;
                }
            }
        }
    }
    cout << "Current position: (" << posi[j]/mazeWidth << ',' << posi[j]%mazeWidth << ')' << endl;
    counter++;
}
cout<<"total steps:"<<counter<<endl;
cout<<"directory steps:"<<counter-counter_dir<<endl;
cout << "Maze solved" << endl;

在这个函数中添加了这一部分，原理为输出时查看记录走过格子次数的数组，如果走过多次，就回溯到最后一次走过时的状态

对于可能情况，如回溯的状态仍在死路中，但这是不可能的，在走入这种情况的前一步，我们就已经回溯到更直接的路径上了。

最后在输出时，对需要回溯的坐标不选择打印，故输出的全是直接路径，且据此得到步数

结果如下

Maze File: maze1.txt
Current position: (0,13)
Current position: (1,13)
Current position: (2,13)
Current position: (3,13)
Current position: (3,12)
Current position: (3,11)
Current position: (3,10)
Current position: (3,9)
Current position: (3,8)
Current position: (3,7)
Current position: (4,7)
Current position: (5,7)
Current position: (5,6)
Current position: (5,5)
Current position: (5,4)
Current position: (5,3)
Current position: (6,3)
Current position: (7,3)
Current position: (7,4)
Current position: (7,5)
Current position: (7,6)
Current position: (7,7)
Current position: (7,8)
Current position: (7,9)
Current position: (8,9)
Current position: (9,9)
Current position: (9,10)
Current position: (9,11)
Current position: (9,12)
Current position: (9,13)
Current position: (10,13)
Current position: (11,13)
Current position: (12,13)
Current position: (13,13)
Current position: (13,14)
Current position: (13,15)
Current position: (14,15)
Current position: (15,15)
Current position: (16,15)
total steps:206
directory steps:39
Maze solved

得到优化结果，直接步数为39步。

任务3

修改迷宫的声明，使其成为指向字符的指针；修改 LoadMaze（），以便动态分配迷宫的空间；使路径数组具有合适的大小；删除在 SolveMaze（） 末尾分配的任何内存。

修改部分如下

int mazeWidth, mazeHeight;
char *maze;
int *posi;
int *post;//对应的指针
int i=0;
bool LoadMaze(const char fname[])
{
    ifstream ifs(fname);
    
    if (ifs.good())
    {
        ifs >> mazeWidth >> mazeHeight;
         maze=new char[mazeWidth*mazeHeight];
         posi=new int[mazeWidth*mazeHeight];
         post=new int[mazeWidth*mazeHeight];//修改尺寸
        for (int i=0;i<mazeHeight;i++)
        {
            for (int j=0;j<mazeWidth;j++)
            {
                ifs >> maze[i*mazeWidth+j];
                post[i*mazeWidth+j]=0;
            }
        }
        ifs.close();
        return true;
    }
    else
    {
        cerr << "File not found." << endl;
        return false;
    }
}
void SolveMaze()
{   
    int pos, other;
    Direction heading;
    
    FindEntrance(pos);
    heading = DOWN;
    while (!AtExit(pos))
    {
        posi[i]=pos;
        post[pos]++;
        i++;
        if(i>=mazeHeight*mazeWidth)
        {
            cout<<"array too small\n";
            abort();//return0；
        }//越界判断
        WheresRight(pos,heading,other);//将面向方向右侧位置传给other
        if (!Wall(other))//右侧无墙，转向右
        {
            TurnRight(heading);//转向
            MoveForward(pos,heading);//在转向后迈步
        }  
        else//是墙，直走
        {
            WheresAhead(pos,heading,other);//生成直走方向
            if (!Wall(other))//前方有路
                MoveForward(pos,heading);//走一步
            else//右边是墙，面前是墙，使当前左转
                TurnLeft(heading);
        }
    }
    posi[i]=pos;
    i++;
    if(i>=mazeHeight*mazeWidth)
    {
        cout<<"array too small\n";
        abort();
    }
    int counter=0;
    int counter_dir=0;
    for(int j=0;j<i;j++)
    {
        if(posi[j]<0)
            continue;
        if(post[posi[j]]>=2)
        {
            int empt=posi[j];
            int cut_num=post[empt]-1;
            int now_num=0;
            for(int h=j+1;h<i;h++,counter_dir++,counter++)
            {
                if(posi[h]==empt)
                {
                    now_num++;
                    if(now_num==cut_num)
                    {
                        j=h;
                        counter++;
                        counter_dir++;
                        break;
                    }
                }
            }
        }
        cout << "Current position: (" << posi[j]/mazeWidth << ',' << posi[j]%mazeWidth << ')' << endl;
        counter++;
    }
    cout<<"total steps:"<<counter<<endl;
    cout<<"directory steps:"<<counter-counter_dir<<endl;
    cout << "Maze solved" << endl;
    delete maze;
    delete posi;
    delete post;//释放内存
}

int mazeWidth, mazeHeight;
char *maze;
int *posi;
int *post;//对应的指针

ifs >> mazeWidth >> mazeHeight;
maze=new char[mazeWidth*mazeHeight];
posi=new int[mazeWidth*mazeHeight];
 post=new int[mazeWidth*mazeHeight];//修改尺寸
delete maze;
delete posi;
delete post;//释放内存

修改为了动态数组的部分，并在结尾处delete释放内存

对maze2.txt和maze3.txt测试结果如下

Maze File: maze2.txt
Current position: (0,20)
Current position: (1,20)
Current position: (1,19)
Current position: (2,19)
Current position: (3,19)
Current position: (3,20)
Current position: (3,21)
Current position: (4,21)
Current position: (5,21)
Current position: (5,20)
Current position: (5,19)
Current position: (6,19)
Current position: (7,19)
Current position: (7,18)
Current position: (7,17)
Current position: (7,16)
Current position: (7,15)
Current position: (8,15)
Current position: (9,15)
Current position: (10,15)
Current position: (11,15)
Current position: (11,14)
Current position: (11,13)
Current position: (12,13)
Current position: (13,13)
Current position: (13,12)
Current position: (13,11)
Current position: (12,11)
Current position: (11,11)
Current position: (11,10)
Current position: (11,9)
Current position: (12,9)
Current position: (13,9)
Current position: (13,8)
Current position: (13,7)
Current position: (13,6)
Current position: (13,5)
Current position: (13,4)
Current position: (13,3)
Current position: (13,2)
Current position: (13,1)
Current position: (14,1)
total steps:260
directory steps:42
Maze solved
-----------------------------------------------------------------------------------------------------
Maze File: maze3.txt
（不水了
total steps:392
directory steps:175
Maze solved

综上，完成了三个部分的要求

代码如下

$maze.h$

/****************************************************
*   Functions to solve mazes.                       *
*                                                   *
*   Datafile must still contain size as first data. *
*                                                   *
*   Four functions are only stubs.                  * 
****************************************************/

#include <iostream>
#include <fstream>
using namespace std;
#ifndef MAZE_H
#define MAZE_H
//  The maze itself is indicated by # for the walls
//  All other locations in the maze can be any other character
//  Global variables defining the maze to be solved

//  These functions provide access to the maze
//  as well as provide manipulation of direction
//  of motion and maze location
//  See implementation for details
struct Position
{
    int H, V;
};
int mazeWidth, mazeHeight;
char *maze;
int *posi;
int *post;
int i=0;
enum Direction {DOWN, LEFT, UP, RIGHT};
void FindEntrance(int&);
bool AtExit(int);
void ReportPosition(int);
void WheresRight(int,Direction,int&);
bool Wall(int);
void TurnRight(Direction&);
void MoveForward(int&,Direction);
void WheresAhead(int,Direction,int&);
void TurnLeft(Direction&);

//  This function loads the maze from the specified file
//  returning the maze and its dimensions
//  The height of the maze is not actually used anywhere but here
//mazeh，w分别是x，y。i设置全局，用于为路径数组定位记录
bool LoadMaze(const char fname[]);


//  This function solves the maze using the 'hand on left wall'
//  rule, printing the maze position as it proceeds

void SolveMaze();
//  This function scans the maze array for the first non-wall item
//  It assumes that the entrance is in the top row of the maze array
    
void FindEntrance(int& pos);
//  This function returns true if the maze position is the exit
//  identified by being in the last row of the array

bool AtExit(int pos);
//  This function displays the position in the maze
//  At this time it specifies row and column of the array

/*void ReportPosition(int pos)
{
    cout << "Current position: (" << pos/mazeWidth << ',' << pos%mazeWidth << ')' << endl;
}*/

//  This function takes a maze position and a heading and determines
//  the position to the right of this position

void WheresRight(int pos, Direction heading, int& right);

//  This function returns true if maze position is wall

bool Wall(int pos);

//  This function changes heading by turning right
//  Take current heading and adjust so that direction is to the right

void TurnRight(Direction& heading);

//  This function changes position in the maze by determining
//  the next position in the current direction

void MoveForward(int& pos, Direction heading);

//  This function determines the position in the direction
//  currently heading

void WheresAhead(int pos, Direction heading, int& ahead);
//  This function changes heading by turning left

void TurnLeft(Direction& heading);

#endif

$maze.cpp$

#include <iostream>
#include <fstream>
#include "Maze.h"
using namespace std;
bool LoadMaze(const char fname[])
{
    ifstream ifs(fname);
    
    if (ifs.good())
    {
        ifs >> mazeWidth >> mazeHeight;
         maze=new char[mazeWidth*mazeHeight];
         posi=new int[mazeWidth*mazeHeight];
         post=new int[mazeWidth*mazeHeight];
        for (int i=0;i<mazeHeight;i++)
        {
            for (int j=0;j<mazeWidth;j++)
            {
                ifs >> maze[i*mazeWidth+j];
                post[i*mazeWidth+j]=0;
            }
        }
        ifs.close();
        return true;
    }
    else
    {
        cerr << "File not found." << endl;
        return false;
    }
}

void SolveMaze()
{   
    int pos, other;
    Direction heading;
    
    FindEntrance(pos);
    heading = DOWN;
    while (!AtExit(pos))
    {
        posi[i]=pos;
        post[pos]++;
        i++;
        if(i>=mazeHeight*mazeWidth)
        {
            cout<<"array too small\n";
            abort();//return0；
        }//越界判断
        WheresRight(pos,heading,other);//将面向方向右侧位置传给other
        if (!Wall(other))//右侧无墙，转向右
        {
            TurnRight(heading);//转向
            MoveForward(pos,heading);//在转向后迈步
        }  
        else//是墙，直走
        {
            WheresAhead(pos,heading,other);//生成直走方向
            if (!Wall(other))//前方有路
                MoveForward(pos,heading);//走一步
            else//右边是墙，面前是墙，使当前左转
                TurnLeft(heading);
        }
    }
    posi[i]=pos;
    i++;
    if(i>=mazeHeight*mazeWidth)
    {
        cout<<"array too small\n";
        abort();
    }
    int counter=0;
    int counter_dir=0;
    for(int j=0;j<i;j++)
    {
        if(posi[j]<0)
            continue;
        if(post[posi[j]]>=2)
        {
            int empt=posi[j];
            int cut_num=post[empt]-1;
            int now_num=0;
            for(int h=j+1;h<i;h++,counter_dir++,counter++)
            {
                if(posi[h]==empt)
                {
                    now_num++;
                    if(now_num==cut_num)
                    {
                        j=h;
                        counter++;
                        counter_dir++;
                        break;
                    }
                }
            }
        }
        cout << "Current position: (" << posi[j]/mazeWidth << ',' << posi[j]%mazeWidth << ')' << endl;
        counter++;
    }
    cout<<"total steps:"<<counter<<endl;
    cout<<"directory steps:"<<counter-counter_dir<<endl;
    cout << "Maze solved" << endl;
    delete maze;
    delete posi;
    delete post;
}
    
void FindEntrance(int& pos)
{
    pos= 0; 
    while (Wall(pos)) pos++;
}

bool AtExit(int pos)
{
    return (pos >= (mazeHeight-1)*mazeWidth);
}


void WheresRight(int pos, Direction heading, int& right)
{
    right=pos;//预处理
    switch (heading) 
    {
    case DOWN://左
        {
            right--;
            break;
        }
    case LEFT://上
        {
            right-=mazeWidth;
            break;
        }
    case UP://右
        {
            right++;
            break;
        }
    case RIGHT://下
        {
            right+=mazeWidth;
        }
    }

}


bool Wall(int pos)
{
    return (maze[pos] == '#');
}


void TurnRight(Direction& heading)
{
    if(heading ==DOWN)//左变
    heading =LEFT;
    else if(heading ==RIGHT)
    heading =DOWN;
    else if(heading ==UP)
    heading =RIGHT;
    else if(heading ==LEFT)
    heading =UP;
}

void MoveForward(int& pos, Direction heading)
{
    switch (heading) 
    {
    case DOWN:
        {
            pos+=mazeWidth;
            break;
        }
    case LEFT:
        {
            pos--;
            break;
        }
    case UP:
        {
            pos-=mazeWidth;
            break;
        }
    case RIGHT:
        {
            pos++;
        }
    }

    //to be finished.
}

void WheresAhead(int pos, Direction heading, int& ahead)
{
    ahead=pos;
    if(heading ==DOWN)//右手在左，面朝下
    ahead+=mazeWidth;
    else if(heading ==RIGHT)//右手在下，面朝右
    ahead++;
    else if(heading ==UP)//右手在右，面朝上
    ahead-=mazeWidth;
    else if(heading ==LEFT)//右手在上，面朝左
    ahead--;
}


void TurnLeft(Direction& heading)
{
    if(heading==DOWN)
    heading=RIGHT;
    else if(heading==LEFT)
    heading=DOWN;
    else if(heading==RIGHT)
    heading=UP;
    else if(heading==UP)
    heading=LEFT;
}

实验心得（灌

1. 理解迷宫遍历算法：通过这个实验，我深入了解了如何使用右手法则遍历迷宫的基本算法原理。这种算法简单而有效，可以帮助找到迷宫的解决方案。
2. 路径优化：删除回溯部分是一个很有趣的挑战。通过避免放置当前位置的副本和优化路径，可以获得更直接的解决方案。这个步骤提高了我对路径优化的理解。
3. 处理任意大小的迷宫：对迷宫程序进行修改，以处理任意大小的迷宫是一个很好的扩展。这个过程需要对内存管理和指针操作有一定的了解，同时也提高了代码的灵活性。
4. 测试和调试：在实验中，测试不同大小的迷宫示例对于验证程序的正确性至关重要。通过测试不同情况下的程序表现，我学会了如何调试和优化代码。
5. 实践能力：这个实验提供了一个很好的机会来将理论知识应用到实际问题中。通过逐步改进和扩展算法，我提高了自己的编程能力和解决问题的能力

优化（水

1.直接路径步数的统计可以换一种算法，更加简便