采用map，queue结合的方式执行广度优先算法，并导出最短路径

#include 
#include 
#include 
#include 
#include 
using namespace std;


struct Node
{
    bool State[4] = {false,false,false,false};
};

bool findMazePathByBFS(vector>& maze, vector>& bestPath)
{
    int Row = maze.size();
    if(Row < 2)
    {
        return false;
    }
    int Column = maze[0].size();
    if(Column < 2)
    {
        return false;
    }
    if(maze[0][0] == 1)
    {
        return false;
    }
    map,Node> mazeMap;
    for(int i = 0;i
        for(int j=0;j
            if(maze[i][j] == 1) //标记每个可通过点右下左上的状态，为1不可通过，继续循环
            {
                continue;
            }
            pair tempPair(i,j);
            Node tempNode;
            if(j+1
                tempNode.State[0] = true;
            }
            if(i+1
                tempNode.State[1] = true;
            }
            if(j-1>=0&&maze[i][j-1] == 0) //左
            {
                tempNode.State[2] = true;
            }
            if(i-1>=0&&maze[i-1][j] == 0) //上
            {
                tempNode.State[3] = true;
            }
            mazeMap[tempPair] = tempNode; //存放在map中，通过坐标可以访问对应的状态
        }
    }
    queue> PointQueue; //用来执行广度优先搜索的队列
    PointQueue.push(make_pair(0,0));//存入起点坐标
    map,pair> ResultMap; //key值为对应每点坐标，value值代表这个点的上一个坐标是啥
    bool isEnabled = false;
    while(PointQueue.size() != 0)
    {
        pair Tmp = PointQueue.front(); //获取队首坐标
        PointQueue.pop();//出队列
        if(mazeMap[Tmp].State[0]) //右可通行
        {
            mazeMap[Tmp].State[0] = false;
            pair RightNode = make_pair(Tmp.first,Tmp.second+1);
            mazeMap[RightNode].State[2] = false; //在右节点中将右节点的左节点，也就是本节点的状态设置为不可通行
            ResultMap[RightNode] = Tmp;
            if(RightNode.first+1 == Row && RightNode.second+1 == Column)
            {
                isEnabled = true;
                break;
            }
            PointQueue.push(RightNode);
        }
        if(mazeMap[Tmp].State[1])//下可通行
        {
            mazeMap[Tmp].State[1] = false;
            pair DownNode = make_pair(Tmp.first+1,Tmp.second);
            mazeMap[DownNode].State[3] = false;
            ResultMap[DownNode] = Tmp;
            if(DownNode.first+1 == Row && DownNode.second+1 == Column)
            {
                isEnabled = true;
                break;
            }
            PointQueue.push(DownNode);
        }
        if(mazeMap[Tmp].State[2]) //左可通行
        {
            mazeMap[Tmp].State[2] = false;
            pair LeftNode = make_pair(Tmp.first,Tmp.second-1);
            mazeMap[LeftNode].State[0] = false;
            ResultMap[LeftNode] = Tmp;
            PointQueue.push(LeftNode);
        }
        if(mazeMap[Tmp].State[3]) //上可通行
        {
            mazeMap[Tmp].State[3] = false;
            pair UpNode = make_pair(Tmp.first-1,Tmp.second);
            mazeMap[UpNode].State[1] = false;
            ResultMap[UpNode] = Tmp;
            PointQueue.push(UpNode);
        }
    }
    cout<<"resultMap size:"<< ResultMap.size()<< endl;
    if(isEnabled)
    {
        stack> sq;
        pair TargetPair = make_pair(Row-1,Column-1);
        sq.push(TargetPair);
        while(!(TargetPair.first == 0 && TargetPair.second == 0))
        {
            pair temp = ResultMap[TargetPair];
            sq.push(temp);
            TargetPair.first = temp.first;
            TargetPair.second = temp.second;
        }
        bestPath.clear();
        while(!sq.empty())
        {
            bestPath.push_back(sq.top());
            sq.pop();
        }
        return true;
    }
    return false;
}
int main()
{
    int a[9][7]={{0,0,0,0,0,0,0},
                 {1,1,1,0,1,1,0},
                 {1,1,1,0,1,1,0},
                 {1,1,0,0,1,0,0},
                 {1,0,0,0,0,1,0},
                 {1,0,1,1,1,0,0},
                 {1,0,1,1,0,0,0},
                 {1,0,1,1,0,1,1},
                 {1,1,1,1,0,0,0}};
    vector> maze(9,vector(7));
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<7;j++)
        {
            maze[i][j] = a[i][j];
        }
    }
    vector> bestPath;
    cout << findMazePathByBFS(maze,bestPath) <
        cout << it.first<<","<
采用map，queue结合的方式执行广度优先算法，并导出最短路径

C/C++/C#相关栏目本月热门文章
