题目要求：
迷宫的两种走法：1 借助于栈 2借助于队列

1实现尽快找到一条可行路径  2找到步数最短的路径

利用文本文件保存地图，easyx图形库显示地图及路径

要求：

1 将程序中C的文件访问方式改为C++流的方式

if (ifs)
 {
  int  a[3];
  for (int i = 0; i < 3; i++)
  {
   ifs>>a[i];

cout<<a[i]<<endl;
    }
 }
 else
  cout << "ifs failed" << endl;

如果已经failed，则可以用clear重置

2 将程序中借助于栈 stack 深度优先找到一条路径的方法，改为借助于 队列 queue 找到最短路径

其它功能自己定义

8 8
2 0 1 0 1 1 0 1
0 1 0 0 0 0 0 1
0 0 0 1 1 1 0 0
1 0 1 1 1 1 0 0
1 0 0 0 0 1 0 1
1 1 1 0 0 1 0 1
0 0 1 1 0 0 0 0
1 0 0 0 0 1 0 3



// maze.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
#include<vector>
#include<stack>
#include<string>
#include<sstream>
#include<iterator>
#include <graphics.h>


using namespace std;


#define N 10   //迷宫最大大小
#define WIDTH 800//显示窗口
#define HEIGHT 600//显示窗口
enum{ROAD,WALL,START,GOAL,OUTOFBORDER=-1};//迷宫地图元素
enum{ CMD_QUIT, CMD_SHOWMAP, CMD_LOADMAP, CMD_RUNNING, CMD_RESETMAP, CMD_SHOWPATH, CMD_CLRSCR, CMD_ERROR };//命令
enum{ NODONE, DONE};//查找辅助标记
enum{ DIRECT_RIGHT, DIRECT_DOWN, DIRECT_LEFT, DIRECT_UP };//方向
void help();//帮助
int getCmd(void);//转换命令


struct PathUnit{
int row;
int col;
int direct;
};
class myMaze{
int map[N][N];//地图
int mark[N][N];//查找辅助
int Col, Row;//行，列
int state;//标示当前地图是否可行
int startRow, startCol;//入口
int outRow, outCol;//出口
vector<PathUnit> path;//路径
public:
//通过一个文本文件保存地图，初始化迷宫
myMaze() {

ZeroMaze();
}
bool loadMap(string mapfile)
{
FILE *pFile = NULL;
int ii= fopen_s(&pFile,mapfile.c_str(), "r");
if (pFile == NULL)
return false;
int value,nResult;
nResult=fscanf_s(pFile, "%d %d", &Row, &Col);//地图行列
if (nResult <= 0 || Row>N-2 || Col>N-2)
{
printf("文件错误，或者地图过大\n");
fclose(pFile);
return false;
}
ZeroMaze();


int startcount = 0;
int outcount = 0;
for (int i = 1; i <= Row;i++)
for (int j = 1; j <= Col; j++)
{
nResult = fscanf_s(pFile, "%d", &value);
if (nResult <= 0)
{
fclose(pFile);
return false;
}
map[i][j] = value;
if (value == START)//起点
{
startcount++;
startRow = i; startCol = j;
}
if (value == GOAL)//目标
{
outcount++;
outRow = i; outCol = j;
}
}
fclose(pFile);
if (outcount != 1 || startcount != 1)//多于一个的起点或出口，地图非法
return false;
mark[startRow][startCol] = DONE;//已走过
state = 1;//已经打开地图
return true;
}
void ZeroMaze()
{
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
{
map[i][j] = OUTOFBORDER;//
mark[i][j] = NODONE;//未走过
}
path.clear();
showline(WIDTH, HEIGHT);
state = 0;//无地图
}
void showline(int w, int h)
{
int unitH = h / N;
int unitW = w / N;
for (int i = 0; i<N; i++)//row
for (int j = 0; j<N; j++)//col
{
rectangle((j)*unitW, (i)*unitH, (j + 1)*unitW, (i + 1)*unitH);
}
}
//显示迷宫
bool ShowMaze(int w,int h)
{
if (state == 0)
return false;
int unitH = h / N;
int unitW = w / N;
COLORREF EnterColor = WHITE;
COLORREF GoalColor = RED;
COLORREF RoadColor = BLUE;
COLORREF WallColor = LIGHTGRAY;
COLORREF OutOfBorderColor = BLACK;


for (int i = 0; i<N; i++)//row
for (int j = 0; j<N;j++)//col
{
switch (map[i][j])
{
case WALL:setfillcolor(WallColor); break;
case ROAD:setfillcolor(RoadColor); break;
case OUTOFBORDER:setfillcolor(OutOfBorderColor); break;
case START:setfillcolor(EnterColor); break;
case GOAL:setfillcolor(GoalColor); break;
}
fillrectangle((j)*unitW, (i)*unitH, (j + 1)*unitW, (i + 1)*unitH);
}
return true;
}
//移动到下一步，四种方向
void GetNextPath(const PathUnit& cur, PathUnit& next)
{
next = cur, next.direct = 0;
switch (cur.direct)
{
case DIRECT_RIGHT: next.col += 1; break;
case DIRECT_DOWN: next.row += 1; break;
case DIRECT_LEFT: next.col -= 1; break;
case DIRECT_UP: next.row -= 1; break;
}

}
//检测是否已经到达出口，矩阵右下角
bool GetOuter(const PathUnit& u)
{
if (map[u.row][u.col] == GOAL)
return true;
return false;
}
bool showpath(int w,int h)
{
if (state != 2)
return false;
int unitH = h / N;
int unitW = w / N;
COLORREF RoadColor = GREEN;
setfillcolor(RoadColor);
  for (int i = path.size()-1; i >=0 ; i--)
   {
    fillellipse((path[i].col)*unitW, (path[i].row)*unitH, (path[i].col + 1)*unitW, (path[i].row + 1)*unitH);
    Sleep(100);
  }
return true;
}
//获取路径
bool GetPath()
{
if (state == 0)
return false;
stack<PathUnit>st;
PathUnit unit;
unit.row = startRow;
unit.col = startCol;
unit.direct = DIRECT_RIGHT;



st.push(unit);
bool bOver = false;
while (!st.empty())
{
PathUnit cur = st.top();
st.pop();
PathUnit next;
while (cur.direct <= 3)//探测单个节点是否可行
{
GetNextPath(cur, next);
if (GetOuter(next))
{
st.push(cur);
st.push(next);
bOver = true;
break;
}
//是一个可行步,没走过，且是新路
if (map[next.row][next.col]==ROAD && mark[next.row][next.col]==NODONE)
{
mark[next.row][next.col] = DONE;

st.push(cur);
cur = next;
}
else
{
cur.direct++;
}
}
if (bOver) break;
}


if (bOver)
{
while (!st.empty())
{
PathUnit& u = st.top();
path.push_back(u);
    string dir;
    switch(u.direct)
    {
    case DIRECT_RIGHT: dir="Right";break;
    case DIRECT_DOWN: dir="Down";break;
    case DIRECT_LEFT: dir="Left";break;
    case DIRECT_UP:  dir="Up";break;
    }
    cout << "(" << u.row << "," << u.col << "," << dir<< ")" << endl;
st.pop();
}
state = 2;//地图找寻到路径
}
else
{
cout << "there is no path" << endl;
}
return true;
}
};


int _tmain(int argc, _TCHAR* argv[])
{
initgraph(WIDTH, HEIGHT, SHOWCONSOLE);
myMaze maze;
help();
int icmd;
while (icmd = getCmd())//quit break while
{
switch (icmd){
case CMD_LOADMAP:if (maze.loadMap("map.txt") == false) cout << "地图未成功打开" << endl; break;//载入地图
case CMD_SHOWMAP:if (maze.ShowMaze(WIDTH,HEIGHT) == false)  cout << "请先打开地图" << endl; break;//显示迷宫地图
case CMD_CLRSCR:clearrectangle(0,0,WIDTH,HEIGHT); break;//清屏
case CMD_RUNNING:if (maze.GetPath() == false) cout << "尚未存在迷宫地图" << endl; break;//查找迷宫路径
case CMD_SHOWPATH:if (maze.showpath(WIDTH, HEIGHT) == false) cout << "还未有路径" << endl; break;//显示路径
case CMD_RESETMAP:clearrectangle(0, 0, WIDTH, HEIGHT); maze.ZeroMaze();  break;//清除地图
case CMD_ERROR:cout << "命令错误" << endl; help(); break;//命令帮助
}
}
system("pause");
closegraph();
return 0;
}
void help()
{
cout << "please input command:showmap loadmap showpath quit running  resetmap clrscr" << endl;
}
int getCmd(void)
{
string cmdstr;
cin >> cmdstr;
if (cmdstr == "resetmap")
return CMD_RESETMAP;
if (cmdstr == "showmap")
return CMD_SHOWMAP;
if (cmdstr == "showpath")
return CMD_SHOWPATH;
if (cmdstr == "loadmap")
return CMD_LOADMAP;
if (cmdstr == "quit")
return CMD_QUIT;
if (cmdstr == "running")
return CMD_RUNNING;
if (cmdstr == "clrscr")
return CMD_CLRSCR;
cout << "command error" << endl;
return CMD_ERROR;
}

用个结构体
struct Position
{
　　　unsigned short x;
　　　unsigned short y;
     int value;
}
表示迷宫中的某个位置。value表示该位置离起点的距离（或步数），起点可定为0,不能通行的地方可随便设个特殊值，如-1
建立整个迷宫的Position二维数组
算法步骤：
1.清空队列，再将起点Position值纳入队列。
2.定义一个Position类型的current变量。
3.再建立循环
bool valid=false;//false表示不能到达终点，true可以到达
while(队列不为空)
{
    取出队头的Position元素用current保存；
    if(current与终点Position的x,y值均相等)
　　{
　　　　　valid=true;//路径已找到
          break;
    }
    检测与current相邻的四个Position是否可以通行，如可以通行，则依次将它们的value域赋为current.value+1,并依次纳入队列。
}
if(valid)
   能到达终点则根据Position数组中各元素value值留下的信息输出路径

可以具体到代码应该怎么处理吗😅我这部分学的实在是不好
完全懵了 老师还叫改成c++风格的输出方式用fsteam实现输出 完全没搞清楚要咋弄

只能做到这步了。没时间具体写。

既然call到我帮忙了~我就试试看~

我没有学过C++,就自学了一些基本模板~还好完成任务啦,哈哈~

VC不支持fopen_s和fscanf_s
改了一下~楼楼用的编译器要记得改回来哦~

#include<iostream>
#include<vector>
#include<stack>
#include<string>
#include<sstream>
#include<iterator>
#include <graphics.h>


using namespace std;


#define N 10               //迷宫最大大小
#define WIDTH 800          //显示窗口
#define HEIGHT 600         //显示窗口

enum
{
    ROAD,
    WALL,
    START,
    GOAL,
    PATH,
    OUTOFBORDER=-1

};                          //迷宫地图元素

enum
{ 
    CMD_QUIT, 
    CMD_SHOWMAP,
    CMD_LOADMAP,
    CMD_RUNNING, 
    CMD_RESETMAP, 
    CMD_SHOWPATH, 
    CMD_CLRSCR, 
    CMD_ERROR 
};  
                        //命令
enum
{ 
    NODONE, 
    DONE
};   
                       //查找辅助标记
enum
{ 
    DIRECT_RIGHT, 
    DIRECT_DOWN, 
    DIRECT_LEFT, 
    DIRECT_UP 
};                     //方向

void help();           //帮助

int getCmd( void );    //转换命令


struct PathUnit
{
    int row;
    int col;
    int direct;

    unsigned int step;   //记录步数
};

class myMaze
{
    int map[N][N];//地图
    int mark[N][N];//查找辅助

    int Col;
    int Row;
    
    //行，列
    int state;//标示当前地图是否可行

    int startRow;
    int startCol;//入口

    int outRow;
    int outCol;//出口

    vector<PathUnit> path;//路径


    public:    //通过一个文本文件保存地图，初始化迷宫
    myMaze() 
    {
        ZeroMaze();
    }

    bool loadMap(string mapfile)
    {
        FILE *pFile = NULL;

        pFile= fopen(mapfile.c_str(), "r");

        if (pFile == NULL)
            return false;

        int value,nResult;
        nResult=fscanf(pFile, "%d %d", &Row, &Col);    //地图行列

        if (nResult <= 0 || Row>N-2 || Col>N-2)
        {
            printf("文件错误，或者地图过大\n");
            fclose(pFile);

            return false;
        }

        ZeroMaze();

        int startcount = 0;
        int outcount = 0;

        for (int i = 1; i <= Row;i++)
            for (int j = 1; j <= Col; j++)
            {
                nResult = fscanf(pFile, "%d", &value);

                if (nResult <= 0)
                {
                    fclose(pFile);
                    return false;
                }

 
                map[i][j] = value;

 
                if (value == START)//起点
                {
                    startcount++;

                    startRow = i; 
                    startCol = j;
                }

                if (value == GOAL)//目标
                { 
                    outcount++;
                    outRow = i; 
                    outCol = j;
                }
            }

        fclose(pFile);

        if (outcount != 1 || startcount != 1    )//多于一个的起点或出口，地图非法
            return false;

        mark[startRow][startCol] = DONE;//已走过

        state = 1;//已经打开地图

        return true;
    }

    void ZeroMaze()
    {
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
            {
                map[i][j] = OUTOFBORDER;    //
                mark[i][j] = NODONE;        //未走过
            }

         path.clear();

         showline(WIDTH, HEIGHT);

         state = 0;//无地图
    }

    void showline(int w, int h)
    {
        int unitH = h / N;
        int unitW = w / N;

        for (int i = 0; i<N; i++)//row
            for (int j = 0; j<N; j++)//col
                rectangle
                (

                    (j + 0)*unitW, 
                    (i + 0)*unitH, 
                    (j + 1)*unitW, 
                    (i + 1)*unitH
                );
    }

     //显示迷宫
    bool ShowMaze(int w,int h)
    {
        if (state == 0)
            return false;

        int unitH = h / N;
        int unitW = w / N;

        COLORREF EnterColor = WHITE;
        COLORREF GoalColor = RED;
        COLORREF RoadColor = BLUE;
        COLORREF WallColor = LIGHTGRAY;
        COLORREF OutOfBorderColor = BLACK;
        COLORREF PathColor = LIGHTGREEN;

        for (int i = 0; i<N; i++)//row
            for (int j = 0; j<N;j++)//col
            {

                switch (map[i][j])
                {

                    case WALL:

                        setfillcolor(WallColor); 

                        break;

                    case ROAD:
                    
                        setfillcolor(RoadColor); 

                        break;

 
                    case OUTOFBORDER:
                     
                        setfillcolor(OutOfBorderColor);
                    
                        break;

                    case START:
                    
                        setfillcolor(EnterColor);
                    
                        break;

                    case GOAL:
                    
                        setfillcolor(GoalColor);
                    
                        break;

                    case PATH:

                        setfillcolor(PathColor);

                        break;
                }

                fillrectangle
                (


                    (j + 0)*unitW, 
                    (i + 0)*unitH, 
                    (j + 1)*unitW, 
                    (i + 1)*unitH
                );

            }

        return true;
    }


    //移动到下一步，四种方向
    void GetNextPath(const PathUnit& cur, PathUnit& next)
    {
        next = cur;
        next.direct = 0;

        switch (cur.direct)
        {
            case DIRECT_RIGHT: 
            
                next.col += 1;

                break;

             case DIRECT_DOWN: 
             
                 next.row += 1; 
             
                 break;

            case DIRECT_LEFT: 

                next.col -= 1;

                break;

            case DIRECT_UP: 

                next.row -= 1;
            
                break;
        }

    }

    //检测是否已经到达出口，矩阵右下角
    bool GetOuter(const PathUnit& u)
    {

        if (map[u.row][u.col] == GOAL)
            return true;

        return false;
    }

    bool showpath(int w,int h)
    {
        if (state != 2)
            return false;

        int unitH = h / N;
        int unitW = w / N;

        COLORREF RoadColor = GREEN;
        setfillcolor(RoadColor);

        for (int i = path.size()-1; i >=0 ; i--)
        {
            fillellipse
            (
        
                (path[i].col + 0)*unitW, 
                (path[i].row + 0)*unitH, 
                (path[i].col + 1)*unitW, 
                  (path[i].row + 1)*unitH
            );

            Sleep(100);
        }

        return true;
    }


    //获取路径
    /*

    bool GetPath()  
    {
        if (state == 0)
            return false;

        stack<PathUnit>st;
    
        PathUnit unit;

        unit.row = startRow;
        unit.col = startCol;
        unit.direct = DIRECT_RIGHT;

        st.push(unit);

        bool bOver = false;

        while (!st.empty())
        {
            PathUnit cur = st.top();
            st.pop();

            PathUnit next;

            while (cur.direct <= 3)//探测单个节点是否可行
            {
                GetNextPath(cur, next);

                if (GetOuter(next))  //判断是否找到出口
                { 
                    st.push(cur);
                    st.push(next);

 
                    bOver = true;

                    break;
                }

                //是一个可行步,没走过，且是新路
                if (map[next.row][next.col]==ROAD && mark[next.row][next.col]==NODONE)
                {

                    mark[next.row][next.col] = DONE;

                    st.push(cur);
                    cur = next;
                }
                else
                    cur.direct++;
            }

            if (bOver) 
                break;
        }
  
        if (bOver)
        {
            while (!st.empty())
            {
                PathUnit& u = st.top();
                path.push_back(u);

                string dir;

                switch(u.direct)
                {
                    case DIRECT_RIGHT: 
                    
                        dir="Right";
                    
                        break;

                    case DIRECT_DOWN: 
                    
                        dir="Down";
                    
                        break;

                    case DIRECT_LEFT: 
                    
                        dir="Left";
                    
                        break;

                    case DIRECT_UP:  
                    
                        dir="Up";
                    
                        break;
                }

                cout << "(" << u.row << "," << u.col << "," << dir<< ")" << endl;

                st.pop();
            }

            state = 2;//地图找寻到路径
        }
        else
             cout << "there is no path" << endl;

        return true;
    }

    */

    bool GetPath()
    {

        if (state==0)
            return false;

        deque<PathUnit>st;

        PathUnit unit;

        unit.row = startRow;
        unit.col = startCol;
        unit.direct = DIRECT_RIGHT;
        unit.step=0;    //起点步数为0

        st.push_front(unit);

        bool bOver=false;

        deque<PathUnit>::iterator iter=st.begin();  //建立迭代器;

        while (iter!=st.end())
        {
            
            PathUnit cur = *iter++;   //获取下一个信息(假出队)

            PathUnit next;

            while (cur.direct <= 3)//探测单个节点是否可行
            {
                GetNextPath(cur, next);    //获取下一个路径

                if (GetOuter(next))    //判断是否找到出口
                { 
                    next.step=cur.step+1;

                    st.push_back(cur);
                    st.push_back(next);

 
                    bOver = true;

                    break;
                }

                 //是一个可行步,没走过，且是新路
                if (map[next.row][next.col]==ROAD && mark[next.row][next.col]==NODONE)
                {

                    mark[next.row][next.col] = DONE;    //标记已经走过的路径

                    next.step=cur.step+1;    //下一步
                    st.push_back(next);
                }

                ++cur.direct;
            }    

             if (bOver) 
                break;
        }

        if (bOver)
        {
            stack<PathUnit>show_st;

            PathUnit& u = st.back();

            while (1)
            {

                st.pop_back();

                if (st.empty())
                    break;

                PathUnit& next=st.back();

                if (next.step==u.step-1)
                {
                    bool flag=false;

                    switch ((u.col-next.col)+N*(u.row-next.row))
                    {

                        case 1: 
                            
                            u.direct=DIRECT_RIGHT;

                            flag=true;

                            break;

                        case -1:

                            u.direct=DIRECT_LEFT;

                            flag=true;

                            break;

                        case N:

                            u.direct=DIRECT_DOWN;

                            flag=true;

                            break;

                        case -N:

                            u.direct=DIRECT_UP;

                            flag=true;

                            break;
                    }

                    if (flag==true)
                    {
                        if (!GetOuter(u))
                            map[u.row][u.col]=PATH;
  
                        show_st.push(u);   //入栈

                        u=st.back();
                    }
                }
            }

            cout << "(" << startRow << "," << startCol << "," << "Start" << ")" << endl;
        
            while (!show_st.empty())
            {
                PathUnit& u = show_st.top();
                path.push_back(u);


                string dir;

            

                switch(u.direct)
                {
                    case DIRECT_RIGHT: 
                    
                        dir="Right";
                    
                        break;

                    case DIRECT_DOWN: 
        
                        dir="Down";
                    
                        break;

                    case DIRECT_LEFT: 
                    
                        dir="Left";
                    
                        break;

                    case DIRECT_UP:  
                    
                        dir="Up";
                    
                        break;
                }

                cout << "(" << u.row << "," << u.col << "," << dir<< ")" << endl;

                show_st.pop();
            }

            state = 2;//地图找寻到路径
        }
        else
             cout << "there is no path" << endl;

        return true;
    }

};


int main(int argc,char* argv[])
{
    initgraph(WIDTH, HEIGHT, SHOWCONSOLE);

    myMaze maze;

    help();

    int icmd;

    while (icmd = getCmd())//quit break while
    {
        switch (icmd)
        {

            case CMD_LOADMAP:
                
                if (maze.loadMap("map.txt") == false) 
                    cout << "地图未成功打开" << endl; 
                
                break;//载入地图

            case CMD_SHOWMAP:
                
                if (maze.ShowMaze(WIDTH,HEIGHT) == false)  
                    cout << "请先打开地图" << endl; 
                
                break;//显示迷宫地图

            case CMD_CLRSCR:
                
                clearrectangle(0,0,WIDTH,HEIGHT); 
                
                break;//清屏

            case CMD_RUNNING:
                
                if (maze.GetPath() == false) 
                    cout << "尚未存在迷宫地图" << endl;
                
                break;//查找迷宫路径

           case CMD_SHOWPATH:
               
               if (maze.showpath(WIDTH, HEIGHT) == false) 
                   cout << "还未有路径" << endl;
               
               break;//显示路径

            case CMD_RESETMAP:
                
                clearrectangle(0, 0, WIDTH, HEIGHT); 
                maze.ZeroMaze(); 
                
                break;//清除地图

             case CMD_ERROR:

                 cout << "命令错误" << endl; help(); 
                 
                 break;//命令帮助
        }
    }

    system("pause");
    closegraph();

    return 0;
}

void help( void )
{

    cout << "please input command:showmap loadmap showpath quit running  resetmap clrscr" << endl;
}

int getCmd( void )
{

    string cmdstr;
    cin >> cmdstr;

    if (cmdstr == "resetmap")
        return CMD_RESETMAP;

    if (cmdstr == "showmap")
        return CMD_SHOWMAP;

    if (cmdstr == "showpath")
        return CMD_SHOWPATH;

    if (cmdstr == "loadmap")
        return CMD_LOADMAP;

    if (cmdstr == "quit")
        return CMD_QUIT;

    if (cmdstr == "running")
        return CMD_RUNNING;

    if (cmdstr == "clrscr")
        return CMD_CLRSCR;

    cout << "command error" << endl;
        return CMD_ERROR;
}

[此贴子已经被作者于2017-12-11 06:16编辑过]